Trapping Rain Water

🎯

Trapping Rain Water

hardMIXEDAmazonGoogleFacebook

Imagine a city skyline after a heavy rainstorm, where water collects between buildings of different heights. How much water is trapped between these buildings?

💡 This problem involves understanding how to calculate trapped water between bars of varying heights. Beginners often struggle because it requires thinking about constraints from both sides simultaneously, which is not straightforward with simple loops.

📋

Problem Statement

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Input: An array of integers height[] representing the elevation map. Output: An integer representing total units of trapped rain water.

1 ≤ n ≤ 10^50 ≤ height[i] ≤ 10^5

💡

Example

Input"[0,1,0,2,1,0,1,3,2,1,2,1]"

Output6

Water trapped at indices 2,4,5,6,9,10 sums to 6 units.

• All bars of same height → 0 trapped water
• Strictly increasing heights → 0 trapped water
• Strictly decreasing heights → 0 trapped water
• Single bar → 0 trapped water

⚠️

Common Mistakes

Not handling empty or single-element arrays

Runtime errors or incorrect trapped water calculation

✅ Add checks for array length before processing

Using min(left_max, right_max) without checking if it's greater than current height

Negative trapped water values added, leading to incorrect results

✅ Ensure trapped water is max(0, min(left_max, right_max) - height[i])

Incorrect pointer movement in two pointer approach

Infinite loops or wrong trapped water calculation

✅ Move pointer with smaller height inward each iteration

Not updating left_max or right_max correctly

Underestimation of trapped water

✅ Update max heights before calculating trapped water at each step

Using nested loops without optimization for large inputs

Time limit exceeded in interviews

✅ Explain brute force but implement optimized approach

🧠

Brute Force (Nested Loops)

💡 This approach is the most straightforward and helps build intuition by directly applying the problem definition, even though it is inefficient.

Intuition

For each bar, find the tallest bar on its left and right, then the water trapped is the minimum of these two heights minus the current bar's height.

Algorithm

1. For each bar, scan all bars to the left to find the maximum height.
2. Scan all bars to the right to find the maximum height.
3. Calculate trapped water at current bar as max(0, min(left_max, right_max) - current height).
4. Sum trapped water for all bars.

💡 The nested loops make it hard to see efficiency, but this directly follows the problem's logic.

</>

Code

def trap(height):
    n = len(height)
    water = 0
    for i in range(n):
        left_max = 0
        for j in range(i + 1):
            left_max = max(left_max, height[j])
        right_max = 0
        for j in range(i, n):
            right_max = max(right_max, height[j])
        water += max(0, min(left_max, right_max) - height[i])
    return water

# Driver code
if __name__ == '__main__':
    print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # Output: 6

Line Notes

n = len(height)Determine the number of bars to iterate over.

for i in range(n)Iterate over each bar to calculate trapped water at that position.

for j in range(i + 1)Find the tallest bar to the left including current bar.

left_max = max(left_max, height[j])Update left_max to the highest bar found so far on the left.

for j in range(i, n)Find the tallest bar to the right including current bar.

right_max = max(right_max, height[j])Update right_max to the highest bar found so far on the right.

water += max(0, min(left_max, right_max) - height[i])Add trapped water at current bar if positive, avoid negative values.

return waterReturn total trapped water after processing all bars.

public class Solution {
    public static int trap(int[] height) {
        int n = height.length;
        int water = 0;
        for (int i = 0; i < n; i++) {
            int left_max = 0;
            for (int j = 0; j <= i; j++) {
                left_max = Math.max(left_max, height[j]);
            }
            int right_max = 0;
            for (int j = i; j < n; j++) {
                right_max = Math.max(right_max, height[j]);
            }
            water += Math.max(0, Math.min(left_max, right_max) - height[i]);
        }
        return water;
    }

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height)); // Output: 6
    }
}

Line Notes

int n = height.length;Get the total number of bars.

for (int i = 0; i < n; i++)Process each bar to compute trapped water.

for (int j = 0; j <= i; j++)Find max height to the left including current bar.

left_max = Math.max(left_max, height[j]);Update left_max with highest bar found so far.

for (int j = i; j < n; j++)Find max height to the right including current bar.

right_max = Math.max(right_max, height[j]);Update right_max with highest bar found so far.

water += Math.max(0, Math.min(left_max, right_max) - height[i]);Add trapped water at current bar if positive, avoid negative values.

return water;Return total trapped water after all bars processed.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int trap(vector<int>& height) {
    int n = height.size();
    int water = 0;
    for (int i = 0; i < n; i++) {
        int left_max = 0;
        for (int j = 0; j <= i; j++) {
            left_max = max(left_max, height[j]);
        }
        int right_max = 0;
        for (int j = i; j < n; j++) {
            right_max = max(right_max, height[j]);
        }
        water += max(0, min(left_max, right_max) - height[i]);
    }
    return water;
}

int main() {
    vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << trap(height) << endl; // Output: 6
    return 0;
}

Line Notes

int n = height.size();Get number of bars in elevation map.

for (int i = 0; i < n; i++)Iterate over each bar to calculate trapped water.

for (int j = 0; j <= i; j++)Find max height to the left including current bar.

left_max = max(left_max, height[j]);Update left_max with highest bar found so far.

for (int j = i; j < n; j++)Find max height to the right including current bar.

right_max = max(right_max, height[j]);Update right_max with highest bar found so far.

water += max(0, min(left_max, right_max) - height[i]);Add trapped water at current bar if positive, avoid negative values.

return water;Return total trapped water after processing all bars.

function trap(height) {
    const n = height.length;
    let water = 0;
    for (let i = 0; i < n; i++) {
        let left_max = 0;
        for (let j = 0; j <= i; j++) {
            left_max = Math.max(left_max, height[j]);
        }
        let right_max = 0;
        for (let j = i; j < n; j++) {
            right_max = Math.max(right_max, height[j]);
        }
        water += Math.max(0, Math.min(left_max, right_max) - height[i]);
    }
    return water;
}

// Test
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // Output: 6

Line Notes

const n = height.length;Determine number of bars in the input array.

for (let i = 0; i < n; i++)Loop through each bar to compute trapped water.

for (let j = 0; j <= i; j++)Find tallest bar to the left including current bar.

left_max = Math.max(left_max, height[j]);Update left_max with highest bar found so far.

for (let j = i; j < n; j++)Find tallest bar to the right including current bar.

right_max = Math.max(right_max, height[j]);Update right_max with highest bar found so far.

water += Math.max(0, Math.min(left_max, right_max) - height[i]);Add trapped water at current bar if positive, avoid negative values.

return water;Return total trapped water after processing all bars.

⏱

Complexity

TimeO(n^2)

SpaceO(1)

For each bar, we scan left and right bars to find max heights, resulting in nested loops and quadratic time.

💡 For n=20 bars, this means about 400 operations, which grows quickly and becomes impractical for large n.

Interview Verdict: TLE for large inputs; useful only to introduce problem and intuition.

This approach is too slow for large inputs but helps understand the problem deeply before optimizing.

🧠

Prefix and Suffix Max Arrays

💡 This approach precomputes maximum heights to the left and right for each bar to avoid repeated scanning, improving efficiency.

Intuition

If we know the tallest bar to the left and right of each bar, we can directly compute trapped water without nested loops.

Algorithm

1. Create an array left_max where left_max[i] is the tallest bar from start to i.
2. Create an array right_max where right_max[i] is the tallest bar from end to i.
3. For each bar, trapped water = max(0, min(left_max[i], right_max[i]) - height[i]).
4. Sum trapped water for all bars.

💡 Precomputing max arrays removes the need for nested loops, making the solution more efficient and easier to understand.

</>

Code

def trap(height):
    n = len(height)
    if n == 0:
        return 0
    left_max = [0] * n
    right_max = [0] * n
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], height[i])
    right_max[n-1] = height[n-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], height[i])
    water = 0
    for i in range(n):
        water += max(0, min(left_max[i], right_max[i]) - height[i])
    return water

# Driver code
if __name__ == '__main__':
    print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # Output: 6

Line Notes

if n == 0:Handle empty input edge case to avoid errors.

left_max = [0] * nInitialize array to store max heights from left.

left_max[0] = height[0]Set first element as starting max from left.

for i in range(1, n)Fill left_max by comparing current height with previous max.

right_max = [0] * nInitialize array to store max heights from right.

right_max[n-1] = height[n-1]Set last element as starting max from right.

for i in range(n-2, -1, -1)Fill right_max by comparing current height with next max.

water += max(0, min(left_max[i], right_max[i]) - height[i])Calculate trapped water at each bar using precomputed maxes, avoid negative values.

public class Solution {
    public static int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;
        int[] left_max = new int[n];
        int[] right_max = new int[n];
        left_max[0] = height[0];
        for (int i = 1; i < n; i++) {
            left_max[i] = Math.max(left_max[i-1], height[i]);
        }
        right_max[n-1] = height[n-1];
        for (int i = n-2; i >= 0; i--) {
            right_max[i] = Math.max(right_max[i+1], height[i]);
        }
        int water = 0;
        for (int i = 0; i < n; i++) {
            water += Math.max(0, Math.min(left_max[i], right_max[i]) - height[i]);
        }
        return water;
    }

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height)); // Output: 6
    }
}

Line Notes

if (n == 0) return 0;Handle empty input to avoid errors.

int[] left_max = new int[n];Create array to store max heights from left.

left_max[0] = height[0];Initialize first element for left max array.

for (int i = 1; i < n; i++)Fill left_max by comparing current height with previous max.

int[] right_max = new int[n];Create array to store max heights from right.

right_max[n-1] = height[n-1];Initialize last element for right max array.

for (int i = n-2; i >= 0; i--)Fill right_max by comparing current height with next max.

water += Math.max(0, Math.min(left_max[i], right_max[i]) - height[i]);Calculate trapped water at each bar using precomputed maxes, avoid negative values.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int trap(vector<int>& height) {
    int n = height.size();
    if (n == 0) return 0;
    vector<int> left_max(n), right_max(n);
    left_max[0] = height[0];
    for (int i = 1; i < n; i++) {
        left_max[i] = max(left_max[i-1], height[i]);
    }
    right_max[n-1] = height[n-1];
    for (int i = n-2; i >= 0; i--) {
        right_max[i] = max(right_max[i+1], height[i]);
    }
    int water = 0;
    for (int i = 0; i < n; i++) {
        water += max(0, min(left_max[i], right_max[i]) - height[i]);
    }
    return water;
}

int main() {
    vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << trap(height) << endl; // Output: 6
    return 0;
}

Line Notes

if (n == 0) return 0;Handle empty input to avoid runtime errors.

vector<int> left_max(n), right_max(n);Create arrays to store max heights from left and right.

left_max[0] = height[0];Initialize first element of left max array.

for (int i = 1; i < n; i++)Fill left_max by comparing current height with previous max.

right_max[n-1] = height[n-1];Initialize last element of right max array.

for (int i = n-2; i >= 0; i--)Fill right_max by comparing current height with next max.

water += max(0, min(left_max[i], right_max[i]) - height[i]);Calculate trapped water at each bar using precomputed maxes, avoid negative values.

function trap(height) {
    const n = height.length;
    if (n === 0) return 0;
    const left_max = new Array(n).fill(0);
    const right_max = new Array(n).fill(0);
    left_max[0] = height[0];
    for (let i = 1; i < n; i++) {
        left_max[i] = Math.max(left_max[i-1], height[i]);
    }
    right_max[n-1] = height[n-1];
    for (let i = n-2; i >= 0; i--) {
        right_max[i] = Math.max(right_max[i+1], height[i]);
    }
    let water = 0;
    for (let i = 0; i < n; i++) {
        water += Math.max(0, Math.min(left_max[i], right_max[i]) - height[i]);
    }
    return water;
}

// Test
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // Output: 6

Line Notes

if (n === 0) return 0;Handle empty input to prevent errors.

const left_max = new Array(n).fill(0);Initialize array to store max heights from left.

left_max[0] = height[0];Set first element as starting max from left.

for (let i = 1; i < n; i++)Fill left_max by comparing current height with previous max.

const right_max = new Array(n).fill(0);Initialize array to store max heights from right.

right_max[n-1] = height[n-1];Set last element as starting max from right.

for (let i = n-2; i >= 0; i--)Fill right_max by comparing current height with next max.

water += Math.max(0, Math.min(left_max[i], right_max[i]) - height[i]);Calculate trapped water at each bar using precomputed maxes, avoid negative values.

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the array multiple times but each traversal is linear, and we use extra arrays of size n.

💡 For n=20 bars, this means about 60 operations plus extra memory for two arrays of size 20.

Interview Verdict: Accepted; efficient for large inputs but uses extra space.

This approach is a common interview solution that balances clarity and efficiency.

🧠

Two Pointer Approach (Optimal)

💡 This approach uses two pointers and constant extra space to achieve linear time, making it the most optimal and elegant solution.

Intuition

Water trapped depends on the smaller of the tallest bars on left and right. By moving pointers inward from both ends, we can calculate trapped water on the fly.

Algorithm

1. Initialize two pointers at start and end of array, and variables to track max heights on both sides.
2. While left pointer is less than right pointer, compare heights at pointers.
3. Move the pointer with smaller height inward, update max height on that side, and add trapped water if current bar is lower than max.
4. Sum trapped water during traversal and return total.

💡 This approach cleverly uses the insight that trapped water depends on the smaller boundary, allowing a single pass with constant space.

</>

Code

def trap(height):
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

# Driver code
if __name__ == '__main__':
    print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # Output: 6

Line Notes

left, right = 0, len(height) - 1Initialize pointers at both ends of the array.

left_max, right_max = 0, 0Track max heights seen so far from left and right.

while left < right:Traverse until pointers meet.

if height[left] < height[right]:Decide which pointer to move based on smaller height.

if height[left] >= left_max:Update left_max if current bar is taller.

water += left_max - height[left]Add trapped water if current bar is lower than left_max.

left += 1Move left pointer inward.

else:Process right pointer similarly.

return waterReturn total trapped water after traversal.

public class Solution {
    public static int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int left_max = 0, right_max = 0;
        int water = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                } else {
                    water += left_max - height[left];
                }
                left++;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    water += right_max - height[right];
                }
                right--;
            }
        }
        return water;
    }

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height)); // Output: 6
    }
}

Line Notes

int left = 0, right = height.length - 1;Initialize pointers at array ends.

int left_max = 0, right_max = 0;Track max heights from left and right.

while (left < right)Loop until pointers meet.

if (height[left] < height[right])Move pointer with smaller height inward.

if (height[left] >= left_max)Update left_max if current bar is taller.

water += left_max - height[left];Add trapped water if current bar is lower than left_max.

left++;Increment left pointer.

elseProcess right pointer similarly.

return water;Return total trapped water.

#include <iostream>
#include <vector>
using namespace std;

int trap(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int left_max = 0, right_max = 0;
    int water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= left_max) {
                left_max = height[left];
            } else {
                water += left_max - height[left];
            }
            left++;
        } else {
            if (height[right] >= right_max) {
                right_max = height[right];
            } else {
                water += right_max - height[right];
            }
            right--;
        }
    }
    return water;
}

int main() {
    vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << trap(height) << endl; // Output: 6
    return 0;
}

Line Notes

int left = 0, right = height.size() - 1;Initialize two pointers at array ends.

int left_max = 0, right_max = 0;Track max heights from left and right sides.

while (left < right)Loop until pointers meet.

if (height[left] < height[right])Move pointer with smaller height inward.

if (height[left] >= left_max)Update left_max if current bar is taller.

water += left_max - height[left];Add trapped water if current bar is lower than left_max.

left++;Increment left pointer.

elseProcess right pointer similarly.

return water;Return total trapped water after traversal.

function trap(height) {
    let left = 0, right = height.length - 1;
    let left_max = 0, right_max = 0;
    let water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= left_max) {
                left_max = height[left];
            } else {
                water += left_max - height[left];
            }
            left++;
        } else {
            if (height[right] >= right_max) {
                right_max = height[right];
            } else {
                water += right_max - height[right];
            }
            right--;
        }
    }
    return water;
}

// Test
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // Output: 6

Line Notes

let left = 0, right = height.length - 1;Initialize two pointers at array ends.

let left_max = 0, right_max = 0;Track max heights from left and right.

while (left < right)Loop until pointers meet.

if (height[left] < height[right])Move pointer with smaller height inward.

if (height[left] >= left_max)Update left_max if current bar is taller.

water += left_max - height[left];Add trapped water if current bar is lower than left_max.

left++;Increment left pointer.

elseProcess right pointer similarly.

return water;Return total trapped water after traversal.

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the array with two pointers and constant extra space.

💡 For n=20 bars, this means about 20 operations and no extra memory, making it very efficient.

Interview Verdict: Accepted; optimal solution for time and space.

This is the best approach to implement in interviews due to its efficiency and elegance.

📊

All Approaches - One-Glance Tradeoffs

💡 The two pointer approach is the best to code in 95% of interviews due to its optimal time and space complexity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Prefix and Suffix Max Arrays	O(n)	O(n)	No	N/A	Good for explaining optimization
3. Two Pointer Approach	O(n)	O(1)	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Start with the brute force approach to show understanding.Explain inefficiencies and propose prefix/suffix max arrays.Finally, present the two pointer optimal solution.Write clean code and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test & Discuss: 3min. Total ~20min

What the Interviewer Tests

Ability to understand problem constraints, optimize naive solutions, and implement efficient code with clear explanations.

Common Follow-ups

• What if the width of bars is not 1? → Multiply trapped water by width.
• Can you solve it using a stack? → Yes, stack-based approach exists.
• How to handle very large inputs efficiently? → Use two pointer approach.
• What if input is streaming? → Two pointer approach is still best with some modifications.

💡 These follow-ups test deeper understanding and ability to adapt solutions to variations.

🔍

Pattern Recognition

When to Use

1) Problem involves trapping or accumulating values between bars. 2) Input is an array representing heights or elevations. 3) Need to find max constraints from both left and right sides. 4) Goal is to calculate total trapped or accumulated quantity.

Signature Phrases

'compute how much water it can trap''elevation map''width of each bar is 1'

NOT This Pattern When

Problems involving only prefix sums or simple sliding windows without two-sided constraints.

Similar Problems

Container With Most Water - focuses on max area between bars, related to two pointer technique.Largest Rectangle in Histogram - uses stack to find max area, related to height constraints.Rain Water Trapped II - extension to 2D grid, similar concept of trapping water.

Practice

1. You are given a sorted array and need to remove duplicates such that each element appears at most twice, modifying the array in-place. Which approach guarantees an optimal O(n) time and O(1) space solution?

easy

A. Using a nested loop to count duplicates and shift elements accordingly

B. Using two pointers where the write pointer only advances if the current element differs from the element two positions before

C. Using a hash map to count occurrences and then reconstruct the array

D. Using dynamic programming to track the maximum allowed duplicates

Solution

1. Step 1: Understand the problem constraints

   The array is sorted, and duplicates are allowed at most twice, so we can leverage order.

2. Step 2: Identify the approach that uses two pointers and index offset check

   This approach compares the current element with the element two positions before the write pointer to decide if it should be written, ensuring O(n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two pointers with index offset check is the known optimal approach [OK]

Hint: Two pointers with offset check is optimal [OK]

Common Mistakes:

• Using nested loops causes O(n²) time
• Hash maps use extra space
• DP is unnecessary here

2. You are given a sorted array of integers and a target sum. You need to find two distinct elements whose sum equals the target. Which approach guarantees an optimal solution in terms of time complexity and correctness?

easy

A. Use two pointers starting at opposite ends of the array, moving inward based on the sum comparison.

B. Use a hash map to store elements and check complements in a single pass.

C. Use dynamic programming to store sums of all pairs and check for the target.

D. Use a greedy approach by iterating from the start and picking the first pair that sums to the target.

Solution

1. Step 1: Understand the problem constraints

   The array is sorted, so two pointers at opposite ends can efficiently find pairs by comparing sums.

2. Step 2: Evaluate each approach

   Greedy fails because it may miss pairs; DP is unnecessary overhead; hash map works but uses extra space and is not optimal for sorted arrays.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers exploit sorting for O(n) time and O(1) space [OK]

Hint: Sorted array + two pointers -> optimal pair search [OK]

Common Mistakes:

• Assuming greedy always works
• Using DP unnecessarily
• Ignoring sorted property

3. What is the time complexity of the optimal 4Sum solution that uses a hash map to store all pairs of sums and then finds complementary pairs to form quadruplets?

medium

A. O(n^2 + k^2), where k is the average number of pairs per sum stored in the hash map.

B. O(n^4) because all quadruplets are checked explicitly.

C. O(n^3) due to nested loops over pairs and quadruplets.

D. O(n^2 log n) because sorting dominates the complexity.

Solution

1. Step 1: Analyze pair sum generation

   Generating all pairs sums takes O(n^2) time and space.

2. Step 2: Analyze combining pairs to quadruplets

   For each sum, combining pairs from two lists takes O(k^2) where k is average pairs per sum.

3. Step 3: Consider worst case

   In worst case, k can be O(n), so combining pairs can be O(n^2) per sum, leading to O(n^4) overall.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Worst-case complexity is O(n^4), not O(n^2 + k^2) [OK]

Hint: Worst-case complexity can be O(n^4) due to pair combinations [OK]

Common Mistakes:

• Assuming average case complexity applies to worst case
• Ignoring worst-case pair combination cost

4. What is the time complexity of the optimal in-place merge algorithm that uses two pointers starting from the end of the arrays to merge two sorted arrays of sizes m and n?

medium

A. O((m + n) log(m + n)) due to sorting after merging

B. O(m * n) because of nested loops comparing elements

C. O(m + n) because each element is processed exactly once

D. O(m + n) but with O(m + n) extra space for temporary storage

Solution

1. Step 1: Identify the loops

   The algorithm uses a single while loop that processes each element from the end once.

2. Step 2: Analyze operations per element

   Each element from nums1 and nums2 is moved at most once, so total operations are proportional to m + n.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time complexity with constant extra space [OK]

Hint: Two-pointer merge is linear time, no sorting needed [OK]

Common Mistakes:

• Confusing with sorting complexity
• Assuming nested loops cause quadratic time

5. The following code attempts to partition an array by parity in-place. Identify the bug that causes incorrect behavior or infinite loops.

medium

A. The condition in the while loop should be i <= len(nums)

B. The variable i should be incremented only when a swap occurs

C. The swap operation should only happen if i > insertPos

D. The insertPos pointer is not incremented after swapping even elements

Solution

1. Step 1: Identify pointer updates

   insertPos is used to track where to place the next even number but is never incremented after a swap.

2. Step 2: Consequence of missing increment

   Without incrementing insertPos, the same position is swapped repeatedly, causing incorrect partition or infinite loop in some variants.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   insertPos must increment after placing an even number [OK]

Hint: insertPos must increment after swapping evens [OK]

Common Mistakes:

• Forgetting to increment insertPos after swap
• Misplacing increment of i inside conditional
• Incorrect loop boundary conditions