Akhilesh

Posted on Feb 12

Master Arrays in 25 Problems: From Novice to Expert

#dsa #leetcode #array #coding

The complete roadmap to dominate array-based coding interviews

Arrays are the foundation of data structures. Master them, and you'll have the pattern recognition needed to solve 40% of all coding interview problems. This guide covers 25 essential problems with both brute force and optimal solutions explained in simple terms.

Why Arrays Matter
Arrays appear everywhere in technical interviews because they test:

Algorithm optimization - Can you improve from O(n²) to O(n)?
Space-time trade-offs - When to use extra memory for speed
Edge case handling - Empty arrays, single elements, duplicates
Pattern recognition - Identifying when to use specific techniques

Core Patterns

Two Pointer Technique When to use: Finding pairs, removing duplicates, sorted arrays

// Template
let left = 0, right = array.length - 1;
while (left < right) {
    // Process elements at left and right
    // Move pointers based on condition
}

Sliding Window When to use: Subarrays, consecutive elements, "size k" problems

// Template
let windowStart = 0;
for (let windowEnd = 0; windowEnd < array.length; windowEnd++) {
    // Expand window
    // Shrink window when needed
}

HashMap for O(1) Lookup When to use: Finding complements, counting frequencies

// Template
const map = new Map();
for (let element of array) {
    if (map.has(target - element)) return true;
    map.set(element, index);
}

Prefix Sum When to use: Range queries, subarray sums

// Template
const prefix = [0];
for (let i = 0; i < array.length; i++) {
    prefix[i + 1] = prefix[i] + array[i];
}
// Range sum [left, right] = prefix[right + 1] - prefix[left]

Problem Solutions

Problem 1: Two Sum
Difficulty: Easy | Platform: LeetCode #1
Problem Statement:
Given an array of integers and a target, return indices of two numbers that add up to target.

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9

Brute Force Approach:

function twoSum(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}

// Time: O(n²) - Nested loops
// Space: O(1) - No extra space

Why brute force fails: For 10,000 elements, this makes 50 million comparisons!
Optimal Solution - HashMap:

function twoSum(nums, target) {
    const map = new Map();

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (map.has(complement)) {
            return [map.get(complement), i];
        }

        map.set(nums[i], i);
    }

    return [];
}

// Time: O(n) - Single pass
// Space: O(n) - HashMap storage

Key Insight: Instead of checking all pairs, remember what we've seen and look for complements.
Pattern: HashMap for complement finding

Problem 2: Best Time to Buy and Sell Stock
Difficulty: Easy | Platform: LeetCode #121
Problem Statement:
Find maximum profit from buying and selling stock once.

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy at 1, sell at 6, profit = 5

Brute Force Approach:

function maxProfit(prices) {
    let maxProfit = 0;

    for (let buy = 0; buy < prices.length; buy++) {
        for (let sell = buy + 1; sell < prices.length; sell++) {
            const profit = prices[sell] - prices[buy];
            maxProfit = Math.max(maxProfit, profit);
        }
    }

    return maxProfit;
}

// Time: O(n²)
// Space: O(1)

Optimal Solution - Track Minimum:

function maxProfit(prices) {
    let minPrice = Infinity;
    let maxProfit = 0;

    for (let price of prices) {
        minPrice = Math.min(minPrice, price);
        maxProfit = Math.max(maxProfit, price - minPrice);
    }

    return maxProfit;
}

// Time: O(n) - Single pass
// Space: O(1)

Key Insight: Track the minimum price seen so far, calculate profit at each step.
Pattern: Tracking extremes while iterating

Problem 3: Contains Duplicate
Difficulty: Easy | Platform: LeetCode #217
Problem Statement:
Return true if any value appears at least twice.

Input: nums = [1,2,3,1]
Output: true

Input: nums = [1,2,3,4]
Output: false

Brute Force:

function containsDuplicate(nums) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] === nums[j]) return true;
        }
    }
    return false;
}

// Time: O(n²)

Better - Sorting:

function containsDuplicate(nums) {
    nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i] === nums[i + 1]) return true;
    }
    return false;
}

// Time: O(n log n) - Due to sorting
// Space: O(1)

Optimal - Set:

function containsDuplicate(nums) {
    const seen = new Set();

    for (let num of nums) {
        if (seen.has(num)) return true;
        seen.add(num);
    }

    return false;
}

// Time: O(n)
// Space: O(n)

// One-liner:
const containsDuplicate = (nums) => new Set(nums).size !== nums.length;
Key Insight: Sets automatically handle uniqueness.
Pattern: Using Set for duplicate detection

Problem 4: Product of Array Except Self
Difficulty: Medium | Platform: LeetCode #238
Problem Statement:
Return array where each element is the product of all other elements. Cannot use division!

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Cannot Use (Division not allowed):

function productExceptSelf(nums) {
    const total = nums.reduce((acc, num) => acc * num, 1);
    return nums.map(num => total / num);
}
// ❌ Violates constraint, fails with zeros
Optimal - Prefix & Suffix Products:
javascriptfunction productExceptSelf(nums) {
    const n = nums.length;
    const result = new Array(n);

    // Left products
    result[0] = 1;
    for (let i = 1; i < n; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }

    // Right products
    let rightProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }

    return result;
}

// Time: O(n)
// Space: O(1) - Output array doesn't count

Visual Breakdown:
nums = [1,2,3,4]

After left products: [1,1,2,6]
After right products: [24,12,8,6]
Key Insight: Build products from left, then multiply with products from right.
Pattern: Prefix/Suffix technique

Problem 5: Maximum Subarray (Kadane's Algorithm)
Difficulty: Medium | Platform: LeetCode #53
Problem Statement:
Find the contiguous subarray with the largest sum.

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has sum = 6

Brute Force:

function maxSubArray(nums) {
    let maxSum = -Infinity;

    for (let i = 0; i < nums.length; i++) {
        let currentSum = 0;
        for (let j = i; j < nums.length; j++) {
            currentSum += nums[j];
            maxSum = Math.max(maxSum, currentSum);
        }
    }

    return maxSum;
}

// Time: O(n²)

Optimal - Kadane's Algorithm:

function maxSubArray(nums) {
    let maxSum = nums[0];
    let currentSum = nums[0];

    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

// Time: O(n)
// Space: O(1)

Key Insight: At each position, decide: start fresh or extend current subarray?

currentSum = Math.max(nums[i], currentSum + nums[i]);
// Translation: "Better to start new here, or keep building?"

Pattern: Dynamic programming, optimal substructure

Problem 6: Move Zeroes
Difficulty: Easy | Platform: LeetCode #283
Problem Statement:
Move all zeros to end while maintaining relative order of non-zeros. Must be in-place!

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Optimal - Two Pointers:

function moveZeroes(nums) {
    let writeIndex = 0;

    // Move all non-zeros to front
    for (let readIndex = 0; readIndex < nums.length; readIndex++) {
        if (nums[readIndex] !== 0) {
            nums[writeIndex] = nums[readIndex];
            writeIndex++;
        }
    }

    // Fill rest with zeros
    for (let i = writeIndex; i < nums.length; i++) {
        nums[i] = 0;
    }
}

// Time: O(n)
// Space: O(1)

Swap Approach (Single Pass):

function moveZeroes(nums) {
    let lastNonZeroIndex = 0;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {
            [nums[lastNonZeroIndex], nums[i]] = [nums[i], nums[lastNonZeroIndex]];
            lastNonZeroIndex++;
        }
    }
}

// Time: O(n)
// Space: O(1)

Pattern: Two-pointer in-place manipulation

Problem 7: Merge Sorted Array
Difficulty: Easy | Platform: LeetCode #88
Problem Statement:
Merge two sorted arrays in-place into the first array.

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Optimal - Merge from End:

function merge(nums1, m, nums2, n) {
    let p1 = m - 1;      // Pointer for nums1
    let p2 = n - 1;      // Pointer for nums2
    let p = m + n - 1;   // Pointer for result position

    while (p2 >= 0) {
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }
}

// Time: O(m + n)
// Space: O(1)

Key Insight: Fill from the end to avoid overwriting elements.
Pattern: Two-pointer merge

Problem 8: Array Manipulation (HackerRank)
Problem Statement:
Given array of size n (all zeros), perform m operations. Each operation adds value k to range [a,b]. Return maximum value after all operations.

n = 5, operations = [[1,2,100], [2,5,100], [3,4,100]]
Output: 200

Brute Force (Times Out):

function arrayManipulation(n, queries) {
    const arr = new Array(n + 1).fill(0);

    for (let [a, b, k] of queries) {
        for (let i = a; i <= b; i++) {
            arr[i] += k;
        }
    }

    return Math.max(...arr);
}

// Time: O(n × m) - Too slow!

Optimal - Difference Array:

function arrayManipulation(n, queries) {
    const diff = new Array(n + 2).fill(0);

    // Mark range boundaries
    for (let [a, b, k] of queries) {
        diff[a] += k;
        diff[b + 1] -= k;
    }

    // Compute prefix sum and find max
    let max = 0;
    let current = 0;
    for (let i = 1; i <= n; i++) {
        current += diff[i];
        max = Math.max(max, current);
    }

    return max;
}

// Time: O(n + m)
// Space: O(n)

Why This Works:

Instead of updating every element in range, mark boundaries
Use prefix sum to calculate actual values
This reduces O(n×m) to O(n+m)

Pattern: Difference array for range updates

Complete Problem List
LeetCode Easy

✅ Two Sum - #1
✅ Best Time to Buy Stock - #121
✅ Contains Duplicate - #217
✅ Maximum Subarray - #53
✅ Merge Sorted Array - #88
✅ Move Zeroes - #283
✅ Plus One - #66
✅ Find Missing Number - #268
✅ Single Number - #136
✅ Intersection of Arrays - #349
✅ Third Maximum Number - #414
✅ Find Disappeared Numbers - #448
✅ Majority Element - #169
✅ Remove Duplicates - #26
✅ Search Insert Position - #35
✅ Pascal's Triangle - #118

LeetCode Medium

✅ Product of Array Except Self - #238

HackerRank

✅ Arrays - DS
✅ 2D Array - DS
✅ Dynamic Array
✅ Left Rotation
✅ Sparse Arrays
✅ Array Manipulation
✅ Minimum Swaps 2
✅ New Year Chaos

Practice Roadmap
Week 1: Foundations
Day 1-2: Two Sum, Contains Duplicate

Master HashMap usage
Understand O(1) lookup

Day 3-4: Best Time to Buy Stock, Move Zeroes

Practice two-pointer technique
In-place manipulation

Day 5-7: Product Except Self, Maximum Subarray

Learn prefix/suffix patterns
Understand Kadane's algorithm

Week 2: Apply Patterns
Days 1-3: All Easy LeetCode problems

Build speed and confidence
Recognize patterns quickly

Days 4-7: HackerRank challenges

Different problem formats
Edge case handling

Week 3: Master Difficulty
Days 1-3: Array Manipulation, New Year Chaos

Handle complex problems
Optimize space/time

Days 4-7: Review and speed practice

Solve problems in < 20 minutes
Practice explaining solutions

Quick Reference Guide

Pattern	When to Use	Example Problem
Two Pointers	Sorted arrays, finding pairs	Two Sum II
Sliding Window	Subarrays of fixed or variable size `k`	Maximum Average Subarray
HashMap	Finding complements or frequency counting	Two Sum
Prefix Sum	Range sum queries, cumulative sums	Subarray Sum Equals K
Kadane's Algorithm	Maximum subarray problems	Maximum Subarray
Difference Array	Efficient range updates	Array Manipulation

Common Pitfalls

1.Off-by-one errors

// ❌ Wrong
for (let i = 0; i <= nums.length; i++)

// ✅ Correct
for (let i = 0; i < nums.length; i++)

2.Not handling empty arrays

if (!nums || nums.length === 0) return 0;

3.Integer overflow (in other languages, JavaScript handles this)

// Safe midpoint calculation
let mid = left + Math.floor((right - left) / 2);

4.Modifying while iterating

// ❌ Don't modify array you're iterating
for (let num of nums) {
    nums.splice(0, 1); // Bad!
}

Next Steps

Practice daily - Solve at least 2 problems
Time yourself - Aim for 20-30 minutes per problem
Review patterns - Identify which pattern applies
Explain out loud - Practice articulating your approach

If you found this helpful, please share and follow for the complete DSA series!

DEV Community

Master Arrays in 25 Problems: From Novice to Expert

The complete roadmap to dominate array-based coding interviews

Problem Solutions

Quick Reference Guide

Top comments (0)