10 Essential Array Programming Challenges for Coding Interviews

Master These Crucial Array Problems to Shine in Your Interview!

1. Two Sum Problem

• Problem: Find two numbers in an array that add up to a specific target.
• Example: Input: nums = [2, 7, 11, 15], target = 9 → Output: [0, 1] (indexes of 2 and 7).
• Approach: Use a hashmap to track the complement of each number.

#include <unordered_map>
std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];
        if (map.count(complement)) return {map[complement], i};
        map[nums[i]] = i;
    }
    return {};
}

2. Maximum Subarray (Kadane’s Algorithm)

• Problem: Find the contiguous subarray with the maximum sum.
• Example: Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → Output: 6 (subarray: [4, -1, 2, 1]).
• Approach: Dynamic programming using Kadane’s Algorithm.

int maxSubArray(std::vector<int>& nums) {
    int maxSum = nums[0], currentSum = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        currentSum = std::max(nums[i], currentSum + nums[i]);
        maxSum = std::max(maxSum, currentSum);
    }
    return maxSum;
}

3. Merge Two Sorted Arrays

• Problem: Merge two sorted arrays into a single sorted array.
• Example: Input: nums1 = [1, 3, 5], nums2 = [2, 4, 6] → Output: [1, 2, 3, 4, 5, 6].
• Approach: Use two pointers.

std::vector<int> mergeSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
    std::vector<int> result;
    int i = 0, j = 0;
    // Merge the two arrays while both have elements left
    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] < nums2[j]) 
            result.push_back(nums1[i++]);  // Add element from nums1
        else 
            result.push_back(nums2[j++]);  // Add element from nums2
    }
    // If nums1 has remaining elements, add them
    while (i < nums1.size()) 
        result.push_back(nums1[i++]);

    // If nums2 has remaining elements, add them
    while (j < nums2.size()) 
        result.push_back(nums2[j++]);

    return result;
}

4. Find Duplicate Number

• Problem: Find the duplicate number in an array of n + 1 integers, where integers are in the range [1, n].
• Example: Input: nums = [3, 1, 3, 4, 2] → Output: 3.
• Approach: Use a slow and fast pointer or a hashmap.

int findDuplicate(std::vector<int>& nums) {
    int slow = nums[0], fast = nums[0];

    // Phase 1: Detect cycle
    do {
        slow = nums[slow];            // Move slow pointer by 1 step
        fast = nums[nums[fast]];      // Move fast pointer by 2 steps
    } while (slow != fast);            // Repeat until slow and fast pointers meet

    // Phase 2: Find the entry point to the cycle (duplicate number)
    fast = nums[0];                    // Start fast pointer from the beginning
    while (slow != fast) {
        slow = nums[slow];             // Move slow pointer by 1 step
        fast = nums[fast];             // Move fast pointer by 1 step
    }

    return slow;                       // The duplicate number (entry point of the cycle)
}

5. Buy and Sell Stock

• Problem: Find the maximum profit from buying and selling stock once.
• Example: Input: prices = [7, 1, 5, 3, 6, 4] → Output: 5 (buy at 1 and sell at 6).
• Approach: Track the minimum price and maximum profit

int maxProfit(std::vector<int>& prices) {
    int minPrice = INT_MAX, maxProfit = 0;

    for (int price : prices) {
        minPrice = std::min(minPrice, price);             // Update minPrice to the lowest value
        maxProfit = std::max(maxProfit, price - minPrice); // Calculate and update maxProfit
    }

    return maxProfit;
}

6. Rotate Array

• Problem: Rotate an array to the right by k steps.
• Example: Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3 → Output: [5, 6, 7, 1, 2, 3, 4].
• Approach: Reverse the array in parts.

void rotateArray(std::vector<int>& nums, int k) {
    k %= nums.size();  // To handle cases where k is larger than the size of the array
    std::reverse(nums.begin(), nums.end());            // Reverse the entire array
    std::reverse(nums.begin(), nums.begin() + k);      // Reverse the first part
    std::reverse(nums.begin() + k, nums.end());        // Reverse the second part
}

7. Find Missing Number

• Problem: Find the missing number in an array of size n containing numbers from 0 to n.
• Example: Input: nums = [3, 0, 1] → Output: 2.
• Approach: Use XOR or sum formulas.

int missingNumber(std::vector<int>& nums) {
    int n = nums.size();
    int totalSum = n * (n + 1) / 2;           // Calculate the sum of numbers from 0 to n
    int arraySum = std::accumulate(nums.begin(), nums.end(), 0);  // Calculate the sum of elements in the array
    return totalSum - arraySum;                // The difference is the missing number
}

8. Trapping Rain Water

• Problem: Find the amount of water trapped after raining on an elevation map.
• Example: Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] → Output: 6.
• Approach: Use two pointers to track the left and right maximums.

int trap(std::vector<int>& height) {
    int left = 0, right = height.size() - 1, leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) leftMax = height[left];
            else water += leftMax - height[left];
            ++left;
        } else {
            if (height[right] >= rightMax) rightMax = height[right];
            else water += rightMax - height[right];
            --right;  // Corrected here
        }
    }
    return water;
}

9. Longest Consecutive Sequence

• Problem: Find the length of the longest consecutive sequence of numbers.
• Example: Input: nums = [100, 4, 200, 1, 3, 2] → Output: 4 (sequence: [1, 2, 3, 4]).
• Approach: Use a set for efficient lookups.

int longestConsecutive(std::vector<int>& nums) {
    std::unordered_set<int> numSet(nums.begin(), nums.end()); // Store all numbers in a set for O(1) lookups
    int longest = 0; // Variable to store the length of the longest consecutive sequence

    for (int num : nums) {
        // Check if num is the start of a sequence (i.e., num-1 is not in the set)
        if (!numSet.count(num - 1)) {
            int currentNum = num, streak = 1; // Initialize current number and streak length

            // Look for consecutive numbers starting from num
            while (numSet.count(currentNum + 1)) {
                currentNum++; // Move to the next consecutive number
                streak++; // Increment the streak length
            }

            // Update the longest streak found
            longest = std::max(longest, streak);
        }
    }

    return longest; // Return the longest consecutive sequence length
}

Product of Array Except Self

• Problem: Return an array such that each element is the product of all elements except itself.
• Example: Input: nums = [1, 2, 3, 4] → Output: [24, 12, 8, 6].
• Approach: Use prefix and suffix products.

std::vector<int> productExceptSelf(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> result(n, 1);  // Initialize result array with 1s.
    int prefix = 1, suffix = 1;     // Prefix and suffix products.

    // First pass: Calculate prefix product and store in result.
    for (int i = 0; i < n; ++i) {
        result[i] *= prefix;         // Multiply the result by the current prefix.
        prefix *= nums[i];           // Update the prefix for the next element.

        result[n - 1 - i] *= suffix; // Multiply the result by the current suffix.
        suffix *= nums[n - 1 - i];    // Update the suffix for the next element.
    }

    return result;  // Return the result array containing the product of elements except itself.
}