Solve Reported OA Coding Problems

The post describes several algorithm questions from an online assessment. The concrete problems that can be reconstructed are:

1. Remove Blocks in a Grid You are given an m x n grid of 0s and 1s, where 1 means a block exists. A block at position (r, c) can be removed only if there is no remaining block in the same row at any column k > c. Remove blocks one at a time until all blocks are gone, and return any valid removal order as a list of coordinates. If multiple answers exist, return any one of them.

2. Find Two Indices for a Target Sum You are given an integer array nums and an integer target. Return two distinct indices i and j such that nums[i] + nums[j] = target. If multiple answers exist, return any valid pair. Aim for linear time.

3. Compute the Minimum Gap You are given an integer array nums. Return the minimum absolute difference between any two distinct elements in the array.

Part 1: Remove Blocks in a Grid

You are given a 0-based m x n grid containing only 0 and 1. A cell (r, c) with value 1 represents a block. You may remove a block only if there is no remaining block in the same row at any column greater than c. Remove blocks one at a time until all blocks are gone, and return one valid removal order as a list of coordinate tuples. If there are no blocks, return an empty list. Any valid order is acceptable; the sample outputs show one possible answer.

Constraints

• 0 <= m, n <= 200
• Each cell is either 0 or 1
• If m > 0, all rows have the same length

Examples

Example 1

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

Explanation: Within each row, blocks must be removed from right to left. The shown output processes row 0 first, then row 1.

Example 2

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

Explanation: In a single row, only the rightmost remaining block can be removed at each step.

Hints

1. Think about one row at a time. In what order must the 1s in a single row be removed?
2. Rows do not affect each other, so once each row order is known, you can combine the rows in any convenient way.

Approach

Approach: per-row right-to-left greedy.

The removal rule says a block at (r, c) may be removed only when no block remains in the same row at any column > c. Rows are independent — a block's eligibility depends solely on what is still present to its right in its own row. So the whole problem decomposes into handling each row separately.

For a single row, if we always peel off the rightmost remaining block first and move leftward, then at the moment we remove any block every block to its right has already been removed, so the rule is satisfied. That is exactly what the code does:

Key steps

• Guard the empty grid (if not grid: return []).
• For each row index r, walk columns from len(row)-1 down to 0.
• Append (r, c) for every cell equal to 1.

Why it's correct. Within a row, blocks are emitted in strictly decreasing column order, so the right-neighbor constraint holds for each removal. Rows never interact, so concatenating each row's order yields a globally valid sequence. The problem allows any valid order, and this is one. The single if not grid guard also covers m = 0; an empty inner row simply contributes nothing.

• Time complexity: O(m * n)
• Space complexity: O(1) auxiliary, excluding the output list (which holds B entries, one per block, B <= m * n)

Part 2: Find Two Indices for a Target Sum

You are given an integer array nums and an integer target. Return two distinct indices i and j such that nums[i] + nums[j] == target. If multiple answers exist, return any one of them. If no such pair exists, return an empty list. Aim for linear time.

Constraints

• 0 <= len(nums) <= 100000
• -10^9 <= nums[i], target <= 10^9
• Indices in the answer must be distinct

Examples

Example 1

Input: ([2, 7, 11, 15], 9)
Output: [0, 1]

Explanation: Because 2 + 7 = 9.

Example 2

Input: ([3, 2, 4], 6)
Output: [1, 2]

Explanation: Because 2 + 4 = 6.

Hints

1. While scanning from left to right, ask what complement value you would need to have seen already.
2. A hash map from value to index can find that complement in O(1) average time.

Part 3: Compute the Minimum Gap

You are given an integer array nums. Return the minimum absolute difference between any two distinct elements in the array. If the array contains fewer than two elements, return None.

Constraints

• 0 <= len(nums) <= 200000
• -10^9 <= nums[i] <= 10^9

Examples

Example 1

Input: ([3, 8, 15, 17],)
Output: 2

Explanation: The smallest difference is 17 - 15 = 2.

Example 2

Input: ([1, 5, 3, 19, 18, 25],)
Output: 1

Explanation: After sorting, 18 and 19 are adjacent and differ by 1.

Hints

1. After sorting, the closest pair must appear next to each other.
2. Be careful with the edge case where the array has fewer than two numbers.