Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Meta SWE coding round with a greedy/array problem that looks straightforward but has a few gotchas once you start thinking about edge cases.

Questions Asked (1)

Given an array of building heights like [5,7,9,4,11], find the minimum total height you need to add (you can only increase, never decrease) so that every adjacent pair of buildings differs by at most 1. The sequence can go up or down.

Algorithms & Data Structures

Author's notes

Spent the first few minutes just staring at the example trying to figure out if this was a DP problem or something greedy.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that you can only increase heights, so the final array must be element-wise >= the original. The problem reduces to finding the minimum non-decreasing (in terms of constraints) sequence that satisfies the adjacent difference constraint and dominates the original. Use a two-pass dynamic programming approach: first enforce the constraint from left to right, then from right to left, taking the maximum of the two passes at each position.

Pro tip: After computing the two passes, the final height at each index is the maximum of the left-to-right and right-to-left values. This ensures both constraints are satisfied while minimizing total added height. Mention that the total added height is the sum of differences between the final and original arrays.

1. Understand the problem and constraints

Restate the problem: given an array, increase elements minimally so that adjacent differences are at most 1. Note that you can only increase, never decrease.

2. Identify the need for two passes

A single pass cannot satisfy both left and right constraints. Explain that you need to propagate constraints from left to right and then from right to left.

3. Perform left-to-right pass

Create an array L where L[0] = original[0], and for i from 1 to n-1, L[i] = max(original[i], L[i-1] - 1). This ensures each element is at least the previous minus 1.

4. Perform right-to-left pass

Create an array R where R[n-1] = original[n-1], and for i from n-2 down to 0, R[i] = max(original[i], R[i+1] - 1). This ensures each element is at least the next minus 1.

5. Combine and compute total added height

For each index i, final[i] = max(L[i], R[i]). The total added height is sum(final[i] - original[i]). Return this sum.

Key Points to Mention

The problem is equivalent to finding the minimal dominating sequence that satisfies the Lipschitz condition with constant 1.
Greedy single-pass approaches fail because they don't account for future constraints.
Two-pass dynamic programming ensures both left and right constraints are satisfied.
The final array is the element-wise maximum of the two passes.
Time complexity is O(n) and space complexity is O(n), which is optimal.
Edge cases: empty array, single element, already valid array.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.