cswork / libraryOpen practice workspace

Coding questions · Uber

Find a Bounded Subarray and Largest Square

This question evaluates array manipulation and algorithmic problem-solving skills across two tasks: enforcing bounded value ranges within contiguous subarrays and identifying largest uniform square regions in binary matrices, exercising concepts such as range-tracking, efficient data structures, and dynamic programming.

Implement the following two independent coding tasks.

Task A: Longest bounded-range subarray

Given an integer array nums and an integer limit, return the length of the longest contiguous subarray such that the difference between the maximum and minimum values inside that subarray is at most limit.

Example:

  • Input: nums = [8, 2, 4, 7], limit = 4
  • Output: 2
  • Explanation: The longest valid subarray is [2, 4] or [4, 7].

Constraints:

  • 1 <= nums.length <= 100000
  • -1000000000 <= nums[i] <= 1000000000
  • 0 <= limit <= 1000000000

Task B: Largest square area in a binary grid

Given an m x n binary matrix grid containing only 0s and 1s, return the area of the largest square containing only 1s.

Example:

  • Input: grid = [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]
  • Output: 4
  • Explanation: The largest all-1 square has side length 2, so its area is 4.

Constraints:

  • 1 <= m, n <= 300
  • grid[i][j] is either 0 or 1.

Part 1: Longest Bounded-Range Subarray

Given an integer array nums and an integer limit, find the length of the longest contiguous subarray such that the difference between the maximum and minimum values inside that subarray is at most limit. You must return only the length, not the subarray itself.

Constraints

  • 1 <= len(nums) <= 100000
  • -1000000000 <= nums[i] <= 1000000000
  • 0 <= limit <= 1000000000

Examples

Example 1

Input: ([8, 2, 4, 7], 4)
Output: 2

Explanation: The longest valid subarrays are [2, 4] and [4, 7], both of length 2.

Example 2

Input: ([10, 1, 2, 4, 7, 2], 5)
Output: 4

Explanation: The subarray [2, 4, 7, 2] has max 7, min 2, and difference 5, so the answer is 4.

Hints

  1. A sliding window is a good fit because the subarray must be contiguous.
  2. To expand and shrink the window efficiently, maintain the current minimum and maximum using monotonic deques.

Part 2: Largest Square Area in a Binary Grid

Given an m x n binary matrix grid containing only 0s and 1s, return the area of the largest square that contains only 1s. The area of a square is its side length multiplied by itself.

Constraints

  • 1 <= m, n <= 300
  • grid[i][j] is either 0 or 1

Examples

Example 1

Input: ([[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]],)
Output: 4

Explanation: The largest all-1 square has side length 2, so its area is 2 * 2 = 4.

Example 2

Input: ([[0,1],[1,0]],)
Output: 1

Explanation: There is no 2x2 square of 1s, but there are individual 1 cells, so the largest area is 1.

Hints

  1. Think about the largest square that can end at each cell.
  2. If a cell contains 1, its square size depends on the top, left, and top-left neighboring cells.