Array & Matrix Interview Problems for Embedded Engineers

Array problems are a staple of embedded engineering interviews. In memory-constrained systems, you work with fixed-size buffers, sensor data arrays, and lookup tables — so interviewers expect you to handle in-place algorithms, two-pointer techniques, and O(1) space solutions fluently. For C language fundamentals, see the C Programming topic pages.

Array Problems

#	Problem	Difficulty	Frequency
1	Trap Rain Water	Hard	★★★★★
2	Meeting Room II	Medium	★★★★★
3	3 Sum	Medium	★★★★★
4	Binary search in sorted array	Easy	★★★★★
5	Continuous Subarray Sum	Medium	★★★★★
6	Random Pick with Weight	Medium	★★★★★
7	House Robber	Medium	★★★★★
8	Decode Ways	Medium	★★★★★
9	Maximum Product Subarray	Medium	★★★★★
10	Maximum Swap	Medium	★★★★★
11	Sort Colors	Medium	★★★★★
12	Find duplicates in 1..100	Easy	★★★★★
13	Smallest and largest in array	Easy	★★★★★
14	Running Sum of 1d Array	Easy	★★★★★
15	Friends Of Appropriate Ages	Medium	★★★★★
16	Degree of an array	Easy	★★★★★
17	Best Time to sell stocks II	Medium	★★★★★
18	Monotonic Array	Easy	★★★★★
19	Longest Continuous Increasing Subsequence	Easy	★★★★★
20	First Missing Positive	Hard	★★★★★
21	Sudoku board validation	Medium	★★★★★

Pattern Cheat Sheet

Pattern	Technique	Problems
Two pointers	Sort + shrink from both ends	3 Sum, Trap Rain Water, Sort Colors
Prefix sum	Running total + hash map for O(1) lookup	Running Sum, Continuous Subarray Sum, Random Pick with Weight
Dynamic programming	Build solution from subproblems	House Robber, Decode Ways, Max Product Subarray
Greedy	Local optimal choice = global optimal	Stocks II, Maximum Swap
Sorting + heap	Sort then process with priority queue	Meeting Rooms II, Friends of Ages
Hash map	O(1) existence checks / counting	First Missing Positive, Find Duplicates, Degree of Array

Implementation

Trap Rain Water Hard ★★★★★

Problem: Given n non-negative integers representing an elevation map, compute how much water it can trap after raining.

QApproach 1 — O(n) time, O(n) space — Stack

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.

cpp

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;
    }
};

QApproach 2 — O(n) time, O(1) space — Two Pointers (preferred)

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.

cpp

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.

Meeting Rooms II Medium ★★★★★

Problem: Given an array of meeting time intervals, find the minimum number of conference rooms required.

QSolution — O(n log n) time, O(n) space — Sort + Min-Heap

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.

cpp

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.

3 Sum Medium ★★★★★

Problem: Given an integer array, find all unique triplets that sum to zero.

QSolution — O(n²) time, O(1) space — Sort + Two Pointers

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.

cpp

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;
    }
};

Continuous Subarray Sum Medium ★★★★★

Problem: Given an integer array and an integer k, return true if the array has a continuous subarray of size at least two whose elements sum up to a multiple of k.

QSolution — O(n) time, O(n) space — Prefix Sum Modulo + Hash Map

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.

cpp

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;
    }
};

Random Pick with Weight Medium ★★★★★

Problem: Given an array of positive integers w, implement pickIndex() that randomly picks an index in proportion to its weight.

QSolution — O(log n) per pick, O(n) space — Prefix Sum + Binary Search

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.

cpp

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;
    }
};

House Robber Medium ★★★★★

Problem: Given an array representing money in each house, return the maximum amount you can rob without robbing two adjacent houses.

QSolution — O(n) time, O(n) space — Dynamic Programming

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.

cpp

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];
    }
};

Decode Ways Medium ★★★★★

Problem: Given a string containing only digits, return the number of ways to decode it where A=1, B=2, ..., Z=26.

QSolution — O(n) time, O(n) space — Dynamic Programming

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.

cpp

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];
    }
};

Maximum Product Subarray Medium ★★★★★

Problem: Given an integer array, find the contiguous subarray that has the largest product.

QSolution — O(n) time, O(1) space — DP with Min/Max Tracking

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 × previous max, or current × previous min.

cpp

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;
    }
};

Maximum Swap Medium ★★★★★

Problem: Given a non-negative integer, swap two digits at most once to get the maximum valued number.

QSolution — O(n) time, O(1) space — Greedy (Right-to-Left Scan)

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.

cpp

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);
    }
};

Sort Colors Medium ★★★★★

Problem: Given an array with objects colored red (0), white (1), or blue (2), sort them in-place in order.

QSolution — O(n) time, O(1) space — Dutch National Flag (Three-Way Partition)

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.

cpp

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.

Running Sum of 1d Array Easy ★★★★★

Problem: Given an array nums, return an array where each element at index i is the sum of all elements from index 0 to i.

QSolution — O(n) time, O(n) space — Prefix Sum

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.

cpp

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.

Friends Of Appropriate Ages Medium ★★★★★

Problem: Given an array of ages, determine the total number of friend requests made based on age conditions.

QApproach 1 — O(n log n) time — Sort + Binary Search

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.

cpp

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;
    }
};

QApproach 2 — O(1) time (bounded) — Counting Array

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

cpp

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;
    }
};

Degree of an Array Easy ★★★★★

Problem: Given a non-empty array, find the smallest length of a contiguous subarray that has the same degree as the array.

QSolution — O(n) time, O(n) space — Hash Maps for Frequency and Position

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.

cpp

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;
    }
};

Best Time to Sell Stocks II Medium ★★★★★

Problem: Given an array of stock prices, find the maximum profit by buying and selling multiple times.

QSolution — O(n) time, O(1) space — Greedy

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.

cpp

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;
    }
};

Monotonic Array Easy ★★★★★

Problem: Given an array, return true if it is monotone increasing or monotone decreasing.

QSolution — O(n) time, O(1) space — Two 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.

cpp

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;
    }
};

Longest Continuous Increasing Subsequence Easy ★★★★★

Problem: Given an unsorted array, find the length of the longest continuous increasing subsequence.

QSolution — O(n) time, O(1) space — Single Pass Counter

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.

cpp

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;
    }
};

First Missing Positive Hard ★★★★★

Problem: Given an unsorted integer array, find the smallest missing positive integer.

QSolution — O(n) time, O(n) space — Hash Set

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.

cpp

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;
    }
};

Matrix Problems

#	Problem	Difficulty	Frequency
1	Diagonal Traverse	Medium	★★★★★

Diagonal Traverse Medium ★★★★★

Problem: Given an m x n matrix, return all elements in diagonal order.

QSolution — O(n×m) time, O(min(n,m)) space — Diagonal Iteration

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.

cpp

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;
    }
};