Katkat
Back

Find a Bounded Subarray and Largest Square

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.