Array & Matrix Interview Problems for Embedded Engineers

Key Insight: When a taller bar appears, water is trapped between it and the previous taller bar in the stack. The stack tracks bars in decreasing height order, and each pop calculates one layer of trapped water.

Thought Process:

1. We need to find, for each bar, the boundaries that contain water above it.
2. A monotonic decreasing stack tracks bars waiting for a taller right boundary.
3. When a taller bar arrives, pop the stack and compute the trapped water between the current bar and the new stack top (the left boundary), using the popped bar as the bottom.
4. Width = current index - stack top index - 1; height = min(left boundary, right boundary) - bottom.

Time Complexity: O(n) — each bar is pushed and popped at most once. Space Complexity: O(n) — stack can hold up to n bars.

Approach: Use a stack to track indices of bars. When the current bar is taller than the bar at the top of the stack, water is trapped between the current bar and the bar below the top. Pop the top, calculate the bounded width and height, and accumulate the water volume.

class Solution {
public:
    int trap(vector<int>& height)
    {
        int ans = 0, current = 0;
        stack<int> st;
        while (current < height.size()) {
            while (!st.empty() && height[current] > height[st.top()]) {
                int top = st.top();
                st.pop();
                if (st.empty())
                    break;
                int distance = current - st.top() - 1;
                int bounded_height = min(height[current], height[st.top()]) - height[top];
                ans += distance * bounded_height;
            }
            st.push(current++);
        }
        return ans;
    }
};

Key Insight: Water at any position is determined by the shorter of the two maximum heights on its left and right. By moving the pointer on the shorter side inward, we guarantee the water level is bounded by the known max on that side.

Thought Process:

1. Brute force: for each bar, scan left and right to find max heights — O(n^2).
2. Precompute left_max[] and right_max[] arrays — O(n) time, O(n) space.
3. Two pointers eliminate the auxiliary arrays: maintain left_max and right_max as running values, and always process the side with the smaller max (since that side determines the water level).
4. This achieves O(n) time with O(1) space — ideal for embedded systems.

Time Complexity: O(n) — single pass through the array. Space Complexity: O(1) — only a few variables.

Approach: Maintain two pointers and track the max height seen from each side. The water at any position is bounded by the shorter of the two max heights. Move the pointer on the shorter side inward, accumulating water as you go. This avoids the stack entirely — ideal for embedded where O(1) space matters.

class Solution {
public:
    int trap(vector<int>& height)
    {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        int left_max = 0, right_max = 0;

        while (left < right) {
            right_max = max(right_max, height[right]);

            if (height[left] < height[right]) {
                if (left_max > height[left]) {
                    ans += (left_max - height[left]);
                } else {
                    left_max = height[left];
                }
                left++;
            } else {
                if (right_max > height[right]) {
                    ans += (right_max - height[right]);
                } else {
                    right_max = height[right];
                }
                right--;
            }
        }

        return ans;
    }
};

Embedded relevance: The two-pointer technique is essential for in-place processing of sensor data streams where you cannot afford auxiliary buffers.

Key Insight: If the earliest-ending ongoing meeting finishes before a new meeting starts, we can reuse that room. A min-heap efficiently tracks the earliest ending time.

Thought Process:

1. Sort meetings by start time so we process them chronologically.
2. Use a min-heap of end times to track all active meetings.
3. For each new meeting, check if the earliest-ending meeting (heap top) has finished — if so, pop it (reuse that room).
4. Push the new meeting's end time. The heap size at the end equals the minimum rooms needed.
5. This mirrors RTOS resource scheduling — determining concurrent resource requirements.

Time Complexity: O(n log n) — sorting dominates; each heap operation is O(log n). Space Complexity: O(n) — heap stores up to n end times.

Approach: Sort meetings by start time. Use a min-heap to track end times of ongoing meetings. For each new meeting, if the earliest-ending meeting has already finished (its end time is before the new start time), reuse that room by popping it. Always push the new meeting's end time. The heap size at the end is the answer.

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());

        priority_queue<int, vector<int>, greater<int>> pq;

        for (auto v : intervals) {
            // reuse room if earliest meeting has ended
            if (!pq.empty() && pq.top() <= v[0]) {
                pq.pop();
            }
            // allocate room for this meeting
            pq.push(v[1]);
        }

        return pq.size();
    }
};

Embedded relevance: This is the same scheduling logic used in RTOS task scheduling — determining the minimum number of concurrent resources (timers, DMA channels, UART ports) needed to service overlapping requests.

Key Insight: Sorting enables two-pointer search for each fixed element, reducing the naive O(n^3) brute force to O(n^2). Duplicate skipping at both levels ensures unique triplets without using a set.

Thought Process:

1. Brute force: check all triplets — O(n^3). Too slow.
2. Sort the array. For each element nums[i], find pairs that sum to -nums[i] using two pointers.
3. Skip duplicate values of nums[i] to avoid duplicate triplets in the outer loop.
4. After finding a valid triplet, skip duplicate values in the inner pointers too.
5. Sorting costs O(n log n), dominated by the O(n^2) two-pointer passes.

Time Complexity: O(n^2) — outer loop O(n) x inner two-pointer O(n). Space Complexity: O(1) — excluding the output array; sorting is in-place.

Approach: Sort the array first. For each element, use two pointers (one at the next element, one at the end) to find pairs that sum to the negative of the current element. Skip duplicates at both the outer loop and inner pointers to avoid duplicate triplets.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int length = nums.size() - 1, left, right;

        for (int index = 0; index <= length; ++index) {
            if (index > 0 && nums[index - 1] == nums[index]) continue;
            left = index + 1;
            right = length;
            while (left < right) {
                int sum = nums[index] + nums[left] + nums[right];
                if (sum < 0) ++left;
                else if (sum > 0) --right;
                else {
                    ans.push_back({nums[index], nums[left], nums[right]});
                    ++left;
                    while (left < right && nums[left] == nums[left - 1]) ++left;
                }
            }
        }
        return ans;
    }
};

Key Insight: If two prefix sums have the same remainder mod k, the subarray between them sums to a multiple of k. This is a direct application of the pigeonhole principle on modular arithmetic.

Thought Process:

1. Brute force: check all subarrays of length >= 2 — O(n^2). Too slow.
2. Prefix sum approach: if prefixSum[j] % k == prefixSum[i] % k, then sum(i+1..j) is divisible by k.
3. Store each remainder's first occurrence index in a hash map.
4. If the same remainder appears again at least 2 positions later, return true.
5. Initialize map with {0: -1} to handle the case where the prefix sum itself is divisible by k.

Time Complexity: O(n) — single pass through the array. Space Complexity: O(n) — hash map stores at most min(n, k) remainders.

Approach: If two prefix sums have the same remainder when divided by k, then the subarray between them sums to a multiple of k. Store each remainder's first occurrence index in a hash map. If the same remainder appears again at least 2 positions later, return true.

The math: if prefixSum[i] % k == prefixSum[j] % k, then (prefixSum[j] - prefixSum[i]) % k == 0, meaning the subarray from i+1 to j sums to a multiple of k.

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if (nums.size() < 2) return false;

        unordered_map<int, int> mp;
        mp[0] = -1;  // handle case where running sum itself is divisible by k

        int runningSum = 0;
        for (int i = 0; i < nums.size(); i++) {
            runningSum += nums[i];

            if (k != 0)
                runningSum = runningSum % k;

            if (mp.find(runningSum) != mp.end()) {
                if (i - mp[runningSum] > 1)
                    return true;
            } else {
                mp[runningSum] = i;
            }
        }
        return false;
    }
};

Key Insight: A prefix sum array maps each index to a range proportional to its weight. Binary searching a random number in [0, totalWeight) finds the correct index in O(log n).

Thought Process:

1. Each index i should be selected with probability w[i] / totalWeight.
2. Build a prefix sum array: index i "owns" the range [prefixSum[i-1], prefixSum[i]).
3. Generate a random number in [0, totalWeight) and find which range it falls into.
4. Binary search on the prefix sum array finds the answer in O(log n).
5. This is the same technique used in weighted random selection for sensor sampling and load balancing.

Time Complexity: O(n) for construction, O(log n) per pickIndex() call. Space Complexity: O(n) — prefix sum array.

Approach: Build a prefix sum array so that each index "owns" a range proportional to its weight. To pick, generate a random number in [0, totalWeight) and binary search for the first prefix sum that exceeds it. This is the same technique used in weighted random selection for sensor sampling and load balancing.

class Solution {
    vector<int> sums;

public:
    Solution(vector<int>& w) {
        sums = vector<int>(w.size(), 0);
        sums[0] = w[0];
        for (int i = 1; i < sums.size(); i++) {
            sums[i] = w[i] + sums[i - 1];
        }
    }

    int pickIndex() {
        int w_index = rand() % (sums.back());

        int st = 0;
        int end = sums.size() - 1;

        while (st < end) {
            int mid = st + (end - st) / 2;
            if (sums[mid] <= w_index) {
                st = mid + 1;
            } else {
                end = mid;
            }
        }

        return st;
    }
};

Key Insight: At each house, the optimal choice depends only on the best results from the previous two houses. This is a linear DP where each state has exactly two predecessors.

Thought Process:

1. Greedy doesn't work — skipping a small house might give access to a much larger one.
2. Define dp[i] = max money robbing houses 0..i.
3. Recurrence: dp[i] = max(dp[i-2] + nums[i], dp[i-1]) — either rob this house (skip previous) or skip this house (keep previous best).
4. Base cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).
5. Can optimize to O(1) space by tracking only prev and prevPrev, but O(n) is clear enough for interviews.

Time Complexity: O(n) — single pass through the array. Space Complexity: O(n) — dp array (optimizable to O(1)).

Approach: Classic DP. At each house, you choose the maximum of: (1) rob this house + best from two houses back, or (2) skip this house and keep the best from the previous house. The recurrence is dp[i] = max(dp[i-2] + nums[i], dp[i-1]). Can be optimized to O(1) space by tracking only the previous two values.

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size() == 0 ? 0 : nums[0];

        vector<int> dp(nums.size(), 0);

        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[nums.size() - 1];
    }
};

Key Insight: Each position can contribute as a single digit (1-9) or as part of a two-digit number (10-26). This creates a Fibonacci-like recurrence with validity constraints on each transition.

Thought Process:

1. This is similar to climbing stairs, but with constraints — not every digit or pair is valid.
2. Define dp[i] = number of ways to decode s[0..i].
3. If s[i] is valid single digit (1-9), add dp[i-1]. If s[i-1..i] is valid two-digit (10-26), add dp[i-2].
4. Edge cases: '0' cannot stand alone, so if s[i] == '0' and s[i-1] is not '1' or '2', the string is invalid (return 0).
5. Watch for consecutive zeros and leading zeros carefully.

Time Complexity: O(n) — single pass through the string. Space Complexity: O(n) — dp array (optimizable to O(1) with two variables).

Approach: Similar to Fibonacci with constraints. At each position, check if the current digit can stand alone (1-9) and if the current + previous digit form a valid two-digit code (10-26). The number of decodings at position i is the sum of valid single-digit and two-digit contributions. Watch for edge cases: leading zeros and consecutive zeros.

class Solution {
public:
    int numDecodings(string s) {
        if (s[0] == '0') return 0;
        if (s.size() == 1) return 1;

        int len = s.size();
        vector<int> dp(len);

        dp[0] = 1;
        dp[1] = (s[0] == '1' || (s[0] == '2' && s[1] < '7') ? 1 : 0) + (s[1] != '0');

        for (int i = 2; i < len; i++) {
            if (s[i] == '0' && (s[i - 1] > '2' || s[i - 1] == '0')) return 0;
            dp[i] = s[i] != '0' ? dp[i - 1] : 0;
            if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] < '7')) dp[i] += dp[i - 2];
        }
        return dp[len - 1];
    }
};

Key Insight: Unlike maximum sum subarray, a negative number can flip a large negative product into the largest positive product. You must track both the running maximum AND minimum products at each position.

Thought Process:

1. Kadane's algorithm doesn't directly work because multiplication by a negative number flips sign.
2. Track both max_so_far and min_so_far at each position.
3. At each element, the new max is max(curr, max_so_far * curr, min_so_far * curr) — the minimum product times a negative element could become the new maximum.
4. Similarly update min_so_far for the same reason (a large positive times a negative could become the new minimum).
5. Zeros reset both running products, which is handled naturally since max(0, ...) and min(0, ...) cover it.

Time Complexity: O(n) — single pass through the array. Space Complexity: O(1) — only tracking three variables.

Approach: Track both the maximum and minimum product ending at each position. The minimum is needed because a negative number can flip a large negative product into the largest positive product. At each step, the new max is the largest of: current element alone, current x previous max, or current x previous min.

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.size() == 0) return 0;

        int max_so_far = nums[0];
        int min_so_far = nums[0];
        int result = max_so_far;

        for (int i = 1; i < nums.size(); i++) {
            int curr = nums[i];
            int temp_max = max(curr, max(max_so_far * curr, min_so_far * curr));
            min_so_far = min(curr, min(max_so_far * curr, min_so_far * curr));
            max_so_far = temp_max;
            result = max(max_so_far, result);
        }

        return result;
    }
};

Key Insight: To maximize the number, we want to swap the leftmost digit that has a larger digit somewhere to its right. Scanning right-to-left while tracking the maximum digit seen so far identifies the optimal swap pair.

Thought Process:

1. Greedy: we want the largest possible digit as far left as possible.
2. Scan right-to-left, tracking the max digit and its position.
3. Whenever we find a digit smaller than the current max, record it as a candidate swap (left = current position, right = max position).
4. The last recorded candidate is the leftmost possible improvement — swap those two digits.
5. If no candidate is found, the number is already maximized.

Time Complexity: O(n) — single pass through the digits (where n is the number of digits). Space Complexity: O(1) — a few tracking variables (string representation is O(n) but bounded by 10 digits for int).

Approach: Scan digits from right to left, tracking the largest digit seen so far and its position. Whenever you find a digit smaller than the current max, record it as a candidate swap. After the full scan, the last recorded candidate gives the optimal swap — the leftmost digit that can be increased by swapping with a larger digit to its right.

class Solution {
public:
    int maximumSwap(int num) {
        string num_str = to_string(num);
        int n = num_str.size();
        int max_val = -1, max_i = -1;
        int left = -1, right = -1;

        for (int i = n - 1; i >= 0; i--) {
            if (num_str[i] > max_val) {
                max_val = num_str[i];
                max_i = i;
            } else if (num_str[i] < max_val) {
                left = i;
                right = max_i;
            }
        }

        if (left == -1) return num;
        swap(num_str[left], num_str[right]);
        return stoi(num_str);
    }
};

Key Insight: The Dutch National Flag algorithm partitions an array into three sections in a single pass using three pointers, without any extra space. The key subtlety: when swapping a 2 to the end, don't advance the current pointer because the swapped-in element hasn't been examined yet.

Thought Process:

1. Counting sort (two passes) works but the interviewer wants a one-pass solution.
2. Three pointers: lo = boundary for 0s, hi = boundary for 2s, i = current scanner.
3. nums[i] == 0: swap with lo, advance both lo and i (swapped-in value is already processed).
4. nums[i] == 2: swap with hi, decrement hi, but do NOT advance i (swapped-in value is unknown).
5. nums[i] == 1: just advance i — 1s naturally end up in the middle.

Time Complexity: O(n) — single pass; each element is visited at most twice. Space Complexity: O(1) — in-place with three pointers.

Approach: Maintain three pointers: lo (boundary for 0s), hi (boundary for 2s), and i (current element). When you see a 0, swap it to the lo region and advance both. When you see a 2, swap it to the hi region but don't advance i (the swapped-in element hasn't been examined yet). When you see a 1, just advance i.

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int lo = 0, hi = nums.size() - 1, i = 0;

        while (i <= hi) {
            if      (nums[i] == 0) { swap(nums[lo++], nums[i++]); }
            else if (nums[i] == 2) { swap(nums[i], nums[hi--]); }
            else                   { i++; }
        }
    }
};

Embedded relevance: Three-way partitioning is used in embedded systems for priority-based message sorting in CAN bus receive buffers — separating high, medium, and low priority frames in a single pass with no extra memory.

Key Insight: Each running sum element depends only on the previous running sum plus the current value. This is the simplest form of prefix sum — the building block for many advanced array techniques.

Thought Process:

1. Initialize result[0] = nums[0].
2. For each subsequent index, result[i] = result[i-1] + nums[i].
3. This can be done in-place (modifying nums directly) for O(1) extra space, but returning a new array is cleaner.
4. This pattern extends to 2D prefix sums, range queries, and difference arrays.

Time Complexity: O(n) — single pass through the array. Space Complexity: O(n) — output array.

Approach: Build the result array iteratively: each element is the previous running sum plus the current value. This is the foundation of prefix sum technique used throughout array problems.

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        vector<int> running_sum(nums.size(), 0);
        running_sum[0] = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            running_sum[i] = nums[i] + running_sum[i - 1];
        }

        return running_sum;
    }
};

Embedded relevance: Prefix sums are the basis for running averages and cumulative sensor readings in embedded data processing — a moving average filter is essentially a windowed prefix sum difference.

Key Insight: For a sorted ages array, binary search efficiently finds the leftmost valid age for each person's friend request window, and caching results by age avoids redundant computation.

Thought Process:

1. Brute force: check all pairs — O(n^2). With n up to 20,000, this is borderline.
2. Sort the array and for each person, binary search for the leftmost valid friend age (> 0.5 * age + 7).
3. Cache results by age value since people of the same age produce the same friend request count.
4. This reduces redundant work when many people share the same age.

Time Complexity: O(n log n) — sorting dominates; binary searches are O(log n) each but cached. Space Complexity: O(n) — sorted array and cache map.

Approach: Sort the ages array. For each person, binary search for the leftmost age that satisfies the friend request condition (age > 0.5 * ageA + 7). Cache results by age to avoid redundant searches.

class Solution {
public:
    unordered_map<int, int> map;

    int findRequests(vector<int>& ages, int index) {
        if (map.find(ages[index]) != map.end()) {
            return map[ages[index]];
        }

        int left = 0;
        int right = index - 1;
        double target = (double)(0.5 * ages[index]) + 7;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (ages[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        map[ages[index]] = index - left;
        return index - left;
    }

    int numFriendRequests(vector<int>& ages) {
        sort(ages.begin(), ages.end());
        int count = 0;
        for (int i = ages.size() - 1; i >= 0; i--) {
            count += findRequests(ages, i);
        }
        return count;
    }
};

Key Insight: Ages are bounded [1, 120], so a counting array reduces the problem from sorting n people to iterating over 120 x 120 age pairs — effectively O(n) since the age-pair loop is constant.

Thought Process:

1. Build a count array of size 121 (ages 0-120).
2. Iterate all 120 x 120 age pairs and apply the friend request conditions.
3. For valid pairs, multiply counts: countA * countB friend requests.
4. When ageA == ageB, subtract countA to avoid self-requests.
5. Total work: O(n) for counting + O(120^2) = O(n) since 14,400 is constant.

Time Complexity: O(n + 120^2) = effectively O(n) since the age-pair loop is bounded constant. Space Complexity: O(1) — fixed-size count array of 121 elements.

Approach: Since ages are bounded [1, 120], use a counting array instead of sorting all 20,000 people. Iterate over all 120x120 age pairs, applying the friend request conditions and multiplying counts. This reduces the problem from O(n log n) to O(n + 120^2) which is effectively O(n).

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        int count[121] = {};
        for (int age : ages) count[age]++;

        int ans = 0;
        for (int ageA = 0; ageA <= 120; ageA++) {
            int countA = count[ageA];
            for (int ageB = 0; ageB <= 120; ageB++) {
                int countB = count[ageB];
                if (ageA / 2 + 7 >= ageB) continue;
                if (ageA < ageB) continue;
                if (ageA < 100 && 100 < ageB) continue;
                ans += (countA * countB);
                if (ageA == ageB) ans -= countA;
            }
        }

        return ans;
    }
};

Key Insight: The shortest subarray with the same degree must contain all occurrences of at least one most-frequent element. For each such element, the subarray spans from its first to last occurrence.

Thought Process:

1. Find the degree (maximum frequency) of the array.
2. For each element with that frequency, the minimum subarray containing all its occurrences spans from first to last index.
3. Track frequency, first occurrence, and last occurrence in hash maps during a single pass.
4. Among all elements with max frequency, return the shortest span.

Time Complexity: O(n) — single pass to build maps, then one scan of results. Space Complexity: O(n) — hash maps for frequency and positions.

Approach: Track each number's frequency and its first/last occurrence positions using hash maps. The array's "degree" is the maximum frequency. For each number with maximum frequency, the shortest subarray containing all its occurrences spans from its first to last position. Return the minimum such span.

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        map<int, int> freq;
        map<int, vector<int>> pos;
        int mx = INT_MIN;

        for (int i = 0; i < nums.size(); i++) {
            mx = max(mx, ++freq[nums[i]]);
            pos[nums[i]].push_back(i);
        }

        int dist = INT_MAX;
        for (auto num : nums) {
            if (freq[num] == mx)
                dist = min(dist, pos[num].back() - pos[num].front());
        }

        return dist + 1;
    }
};

Key Insight: With unlimited transactions, the maximum profit equals the sum of all positive day-over-day differences. Any upward movement can be captured, and there's no penalty for buying and selling on the same day.

Thought Process:

1. With unlimited transactions, we want to capture every upward price movement.
2. Mathematically, buying at every local minimum and selling at every local maximum is equivalent to summing all positive consecutive differences.
3. If prices[i] > prices[i-1], add the difference to profit. Otherwise, skip.
4. This greedy approach works because capturing every positive delta is provably optimal.
5. No need to track buy/sell states — just accumulate gains.

Time Complexity: O(n) — single pass through prices. Space Complexity: O(1) — one variable for running profit.

Approach: Collect every uphill profit. Whenever today's price is higher than yesterday's, add the difference to the total profit. This is equivalent to buying at every local minimum and selling at every local maximum, but simpler to implement — just sum all positive day-over-day differences.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int prev = prices[0], res = 0;
        for (int curr : prices) {
            if (prev < curr) res += curr - prev;
            prev = curr;
        }
        return res;
    }
};

Key Insight: Track two boolean flags simultaneously. If neither monotone increasing nor monotone decreasing survives the full scan, the array is not monotonic. Early termination when both flags become false avoids unnecessary work.

Thought Process:

1. The array is monotonic if it's entirely non-decreasing OR entirely non-increasing.
2. Maintain two booleans: increasing (no pair where A[i] > A[i+1]) and decreasing (no pair where A[i] < A[i+1]).
3. Scan adjacent pairs — violations flip the corresponding flag to false.
4. If both become false, return false immediately (early exit).
5. After the scan, return true — at least one direction held.

Time Complexity: O(n) — single pass through adjacent pairs. Space Complexity: O(1) — two boolean flags.

Approach: Maintain two boolean flags: increasing and decreasing, both starting true. Scan adjacent pairs — if any pair is strictly decreasing, set increasing = false; if strictly increasing, set decreasing = false. If both become false, return false early. Otherwise, the array is monotonic in at least one direction.

class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        bool increase = true;
        bool decrease = true;
        for (int i = 0; i + 1 < (int)A.size(); i++) {
            if (A[i] > A[i + 1]) increase = false;
            if (A[i] < A[i + 1]) decrease = false;
            if (!increase && !decrease) return false;
        }
        return true;
    }
};

Key Insight: This is a simple streak-counting problem. Extend the current streak while elements are strictly increasing; reset to 1 when they aren't. Track the maximum streak across the entire array.

Thought Process:

1. Initialize count = 1 (minimum subsequence length) and answer = 1.
2. Compare each pair of adjacent elements.
3. If nums[i] < nums[i+1], extend the streak (count++) and update answer.
4. Otherwise, reset count to 1 — the streak is broken.
5. This is the same pattern used for detecting rising edges in sensor data.

Time Complexity: O(n) — single pass through the array. Space Complexity: O(1) — two integer variables.

Approach: Walk through the array tracking the current streak length. When the next element is greater than the current, extend the streak. Otherwise, reset to 1. Track the maximum streak seen across the entire scan.

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        int answer = 1, count = 1;
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums[i] < nums[i + 1]) {
                count++;
                answer = max(answer, count);
            } else {
                count = 1;
            }
        }
        return answer;
    }
};

Key Insight: The answer must be in range [1, n+1] where n is the array length (by pigeonhole principle). Using a hash set for O(1) lookups, scan from 1 upward to find the first missing value.

Thought Process:

1. The smallest missing positive is at most n+1 (when array contains exactly 1..n).
2. Insert all positive numbers into a hash set for O(1) lookup.
3. Iterate from 1 upward — the first number not in the set is the answer.
4. An O(1) space solution exists by using the array itself as a hash table (place value v at index v-1), but the hash set approach is clearer for interviews.
5. Mention both approaches to show awareness of the space optimization.

Time Complexity: O(n) — building set + scanning. Space Complexity: O(n) — hash set (can be O(1) with in-place index mapping, but that approach is trickier).

Approach: Insert all positive numbers into a hash set. Then iterate from 1 upward, returning the first number not found in the set. Note: an O(1) space solution exists by using the input array itself as a hash table (placing each value at its corresponding index), but the hash set approach is clearer for interviews.

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_map<int, int> umap;
        int max_v = 0;

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) {
                umap[nums[i]] = 1;
                max_v = max(max_v, nums[i]);
            }
        }

        for (int i = 1; i < max_v; i++) {
            if (umap.find(i) == umap.end())
                return i;
        }

        return max_v + 1;
    }
};

Key Insight: The matrix has rows + cols - 1 diagonals. Each diagonal can be collected bottom-left to top-right, then reversed for even-numbered diagonals to create the zigzag pattern.

Thought Process:

1. Number the diagonals 1 through (rows + cols - 1).
2. For each diagonal k, determine the starting row and column based on whether k exceeds the row count.
3. Walk each diagonal by decrementing row and incrementing column until out of bounds.
4. For even-numbered diagonals, reverse the collected elements to achieve the zigzag traversal.
5. Append each diagonal's elements to the result array.

Time Complexity: O(nm) — every element is visited exactly once. Space Complexity: O(min(n,m)) — temporary diagonal buffer (output array is O(nm) but not counted as extra space).

Approach: The matrix has rows + cols - 1 diagonals. For each diagonal, collect elements by walking from bottom-left to top-right (decrement row, increment column). For even-numbered diagonals, reverse the collected elements to achieve the zigzag pattern. The starting row and column for each diagonal depend on whether the diagonal index exceeds the number of rows.

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        if (rows == 0) return vector<int>();

        int cols = matrix[0].size();
        if (cols == 0) return vector<int>();

        int dig_size = rows + cols - 1;

        vector<int> ret;
        int i = 0, j = 0;
        for (int k = 1; k <= dig_size; k++) {
            vector<int> diag{};
            i = k >= rows ? rows - 1 : k - 1;
            j = k >= rows ? k - rows : 0;
            while (i >= 0 && j < cols) {
                diag.push_back(matrix[i][j]);
                i--;
                j++;
            }
            if (k % 2 == 0)
                reverse(diag.begin(), diag.end());
            ret.insert(ret.end(), diag.begin(), diag.end());
        }

        return ret;
    }
};

Key Insight: You can't sort (modifies array), can't use a hash set (O(n) space). The trick is to binary search on the value range [1, n], not the array indices. For any midpoint mid, count how many array elements are <= mid. By the pigeonhole principle, if count > mid, the duplicate must be in [1, mid].

Thought Process:

1. What approaches are off the table? Sorting (modifies array), hash set (O(n) space), marking visited by negating (modifies array).
2. Binary search on value range: the values are in [1, n]. Pick mid = (1+n)/2. Count elements <= mid. If count > mid, by pigeonhole, the lower half contains the duplicate.
3. Each binary search iteration does an O(n) scan, and we do O(log n) iterations, giving O(n log n) total.
4. Even better approach: Floyd's cycle detection. Treat nums[i] as a "next pointer" — since there's a duplicate, the implicit linked list has a cycle. The cycle entrance is the duplicate value. This achieves O(n) time.
5. In an interview, mention both approaches. Binary search is easier to implement correctly; Floyd's is more elegant.

Time Complexity: O(n log n) for binary search approach. O(n) for Floyd's cycle detection. Space Complexity: O(1) for both approaches.

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int left = 1, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = 0;
            for (int num : nums) {
                if (num <= mid) count++;
            }
            if (count > mid) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};

Embedded relevance: The pigeonhole principle applied to value ranges is used in memory leak detection — if you allocate n buffers but find n+1 references, one must be a duplicate handle. Binary search on the address range identifies the collision.