Katkat
Back

Solve Three Array and Matrix Path Problems

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Tests multi-paradigm algorithmic fluency across dynamic programming with auxiliary states, greedy interval coverage, and monotonic deque optimization for bounded subarrays.

Problem Statement

Implement solutions for three algorithmic problems covering matrix traversal, interval coverage, and subarray optimization.

Task 1: Minimum Cost Path with at Most One Diagonal Move

Given an m x n integer grid grid, find the minimum path sum from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1). You can move right (r, c + 1) or down (r + 1, c). In addition, you may make at most one diagonal move (r + 1, c + 1) during the entire traversal.

def min_cost_path(grid: list[list[int]]) -> int:

Task 2: Minimum Interval Coverage

Given a list of closed intervals intervals where intervals[i] = [start_i, end_i] and a target interval target = [T_start, T_end], return the minimum number of intervals required to completely cover [T_start, T_end]. If it is impossible to fully cover the target, return -1.

def min_intervals(intervals: list[list[int]], target: list[int]) -> int:

Task 3: Maximum Subarray Sum with Bounded Length

Given an integer array nums (which may contain negative values) and an integer k, return the maximum possible sum of any non-empty contiguous subarray of length at most k.

def max_subarray_bounded(nums: list[int], k: int) -> int:

Examples

Example 1 (Task 1)

Input: grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]
Output: 6
Explanation: Path: (0,0) [1] -> diagonal to (1,1) [5] -> down to (2,1) [2] -> right to (2,2) [1] gives 1 + 5 + 2 + 1 = 9.
Better: (0,0) [1] -> down to (1,0) [1] -> diagonal to (2,1) [2] -> right to (2,2) [1] gives 1 + 1 + 2 + 1 = 5.
Even better: (0,0) [1] -> down to (1,0) [1] -> down to (2,0) [4] -> ... wait, 1 + 1 + 2 + 1 = 5.
Best valid path sum is 5.

Example 2 (Task 2)

Input: intervals = [[0, 3], [3, 7], [1, 5], [4, 9]], target = [1, 8]
Output: 2
Explanation: Select [1, 5] and [4, 9], covering [1, 8] with 2 intervals.

Example 3 (Task 3)

Input: nums = [2, -1, 4, 3, -2], k = 2
Output: 7
Explanation: Subarray [4, 3] has length 2 <= 2 and sum 7.

Constraints

  • Task 1: 1 <= m, n <= 300, 0 <= grid[r][c] <= 1000
  • Task 2: 1 <= len(intervals) <= 10^5, intervals[i][0] <= intervals[i][1], -10^9 <= start_i, end_i, T_start, T_end <= 10^9
  • Task 3: 1 <= len(nums) <= 10^5, 1 <= k <= len(nums), -10^4 <= nums[i] <= 10^4

Edge Cases

  • Task 1: A 1 x 1 grid should return grid[0][0]. Grids with 1 row or 1 column cannot use diagonal moves.
  • Task 2: Intervals might touch at boundary points (e.g., [1, 3] and [3, 5] cover [1, 5]). Redundant intervals should be bypassed.
  • Task 3: When all elements are negative, the answer should be the maximum single negative element.

Hints

Hint 1

For Task 1, define dp[r][c][used] where used in {0, 1} represents whether the single diagonal move has already been taken.

Hint 2

For Task 2, sort intervals by start position and greedily pick the interval that extends the covered boundary the furthest among all valid candidates.

Hint 3

For Task 3, express subarray sums as P[i] - P[j] with i - k <= j < i, and use a monotonic deque to maintain the minimum prefix sum P[j] in the sliding window.

Follow-up questions

  • In Task 1, how would the state complexity change if up to d diagonal moves were allowed, and can we optimize space from O(m * n * d) to O(n * d)?
  • In Task 2, how would you modify the algorithm to return the exact subset of interval indices used, minimizing total overlap length as a secondary objective?
  • In Task 3, how would you solve the problem if the subarray length had both a lower and upper bound (i.e., a <= length <= b)?