Mastering Array Patterns for Technical Interviews

A comprehensive guide to the 10 most important array patterns in Data Structures and Algorithms.

Introduction
Pattern 1: Traversal
Pattern 2: Two Pointers
Pattern 3: Sliding Window
Pattern 4: Prefix Sum
Pattern 5: Kadane's Algorithm
Pattern 6: Binary Search on Arrays
Pattern 7: Sorting-Based Patterns
Pattern 8: Hashing with Arrays
Pattern 9: In-Place Modification
Pattern 10: Cyclic Sort
Study Plan
Practice Problems

Introduction

Arrays are the foundation of most Data Structures and Algorithms problems. While there are countless array problems, most can be solved using 8-10 core patterns. Mastering these patterns will dramatically improve your problem-solving speed and interview performance.

This guide covers:

What each pattern is
When to use it
How to implement it
Real examples with working code

Each pattern is explained with clear theory, time/space complexity analysis, and practical JavaScript implementations.

Pattern 1: Traversal

Traversal Theory

Array traversal is the most fundamental pattern. It involves iterating through an array from start to end (or end to start) to process each element. While simple, it's the building block for many complex algorithms.

Key Concepts:

Sequential access to each element
Single pass through the array
Maintains running state (counters, max/min values, etc.)
Foundation for more complex patterns

Time Complexity: O(n) - visits each element once Space Complexity: O(1) - only uses variables for state

Traversal When to Use

Use traversal pattern when you need to:

Count elements matching a condition
Find minimum or maximum values
Check if all/any elements satisfy a condition
Calculate frequency of elements
Compute aggregate values (sum, product, etc.)
Transform each element

Traversal Implementation

// Basic traversal template
function traverse(arr) {
  for (let i = 0; i < arr.length; i++) {
    // Process arr[i]
    console.log(arr[i]);
  }
}

// Alternative: for...of loop (cleaner when index not needed)
function traverseForOf(arr) {
  for (let element of arr) {
    // Process element
    console.log(element);
  }
}

// Alternative: forEach method
function traverseForEach(arr) {
  arr.forEach((element, index) => {
    // Process element at index
    console.log(element, index);
  });
}

Traversal Examples

Example 1: Find Maximum Element

/**
 * Find the maximum element in an array
 * @param {number[]} arr - Input array
 * @return {number} - Maximum value
 */
function findMax(arr) {
  if (arr.length === 0) return -Infinity;
  
  let max = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  
  return max;
}

// Alternative: using Math.max
function findMaxConcise(arr) {
  return Math.max(...arr);
}

// Test
console.log(findMax([3, 7, 2, 9, 1])); // 9

Example 2: Count Even Numbers

/**
 * Count how many even numbers are in the array
 * @param {number[]} arr - Input array
 * @return {number} - Count of even numbers
 */
function countEven(arr) {
  let count = 0;
  
  for (let num of arr) {
    if (num % 2 === 0) {
      count++;
    }
  }
  
  return count;
}

// Test
console.log(countEven([1, 2, 3, 4, 5, 6])); // 3

Example 3: Calculate Sum and Average

/**
 * Calculate sum and average of array elements
 * @param {number[]} arr - Input array
 * @return {object} - Object with sum and average
 */
function sumAndAverage(arr) {
  if (arr.length === 0) {
    return { sum: 0, average: 0 };
  }
  
  let sum = 0;
  
  for (let num of arr) {
    sum += num;
  }
  
  return {
    sum: sum,
    average: sum / arr.length
  };
}

// Test
console.log(sumAndAverage([10, 20, 30, 40])); // { sum: 100, average: 25 }

Pattern 2: Two Pointers

Two Pointers Theory

The two pointers pattern uses two variables (pointers) to track positions in an array. These pointers typically move toward each other or in the same direction, allowing us to solve problems in O(n) time instead of O(n²).

Key Concepts:

Two indices tracking different positions
Common approaches:
- Opposite direction: Start from both ends, move toward center
- Same direction: Both move left to right (fast/slow pointers)
Reduces time complexity from O(n²) to O(n)
Works best on sorted arrays

Time Complexity: O(n) - each pointer traverses at most once Space Complexity: O(1) - only uses two pointer variables

Two Pointers When to Use

Use two pointers when:

Array is sorted (or can be sorted)
Looking for pairs with specific properties
Removing duplicates in-place
Reversing an array
Palindrome problems
Partitioning problems

Two Pointers Implementation

// Template 1: Opposite direction (converging)
function twoPointersOpposite(arr) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left < right) {
    // Process arr[left] and arr[right]
    
    // Move pointers based on condition
    if (someCondition) {
      left++;
    } else {
      right--;
    }
  }
}

// Template 2: Same direction (fast and slow)
function twoPointersSame(arr) {
  let slow = 0;
  let fast = 0;
  
  while (fast < arr.length) {
    // Process elements
    
    if (someCondition) {
      slow++;
    }
    fast++;
  }
}

Two Pointers Examples

Example 1: Two Sum on Sorted Array

/**
 * Find two numbers that add up to target in a sorted array
 * @param {number[]} arr - Sorted array
 * @param {number} target - Target sum
 * @return {number[]} - Indices of the two numbers
 */
function twoSumSorted(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left < right) {
    const sum = arr[left] + arr[right];
    
    if (sum === target) {
      return [left, right];
    } else if (sum < target) {
      left++; // Need larger sum, move left pointer right
    } else {
      right--; // Need smaller sum, move right pointer left
    }
  }
  
  return []; // No solution found
}

// Test
console.log(twoSumSorted([1, 3, 5, 7, 9], 12)); // [2, 4] (5 + 7 = 12)

Example 2: Remove Duplicates from Sorted Array

/**
 * Remove duplicates in-place from sorted array
 * Returns new length of array with unique elements
 * @param {number[]} arr - Sorted array
 * @return {number} - New length
 */
function removeDuplicates(arr) {
  if (arr.length === 0) return 0;
  
  let slow = 0; // Position for next unique element
  
  for (let fast = 1; fast < arr.length; fast++) {
    if (arr[fast] !== arr[slow]) {
      slow++;
      arr[slow] = arr[fast];
    }
  }
  
  return slow + 1; // New length
}

// Test
const arr = [1, 1, 2, 2, 3, 4, 4];
const newLength = removeDuplicates(arr);
console.log(arr.slice(0, newLength)); // [1, 2, 3, 4]

Example 3: Valid Palindrome

/**
 * Check if string is a palindrome (ignoring non-alphanumeric)
 * @param {string} s - Input string
 * @return {boolean} - True if palindrome
 */
function isPalindrome(s) {
  // Convert to lowercase and keep only alphanumeric
  const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  
  let left = 0;
  let right = cleaned.length - 1;
  
  while (left < right) {
    if (cleaned[left] !== cleaned[right]) {
      return false;
    }
    left++;
    right--;
  }
  
  return true;
}

// Test
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true

Example 4: Container With Most Water

/**
 * Find two lines that together with x-axis forms container with most water
 * @param {number[]} height - Array of heights
 * @return {number} - Maximum area
 */
function maxArea(height) {
  let left = 0;
  let right = height.length - 1;
  let maxWater = 0;
  
  while (left < right) {
    // Calculate area with current two lines
    const width = right - left;
    const minHeight = Math.min(height[left], height[right]);
    const area = width * minHeight;
    
    maxWater = Math.max(maxWater, area);
    
    // Move pointer with smaller height
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  
  return maxWater;
}

// Test
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49

Pattern 3: Sliding Window

Sliding Window Theory

The sliding window pattern maintains a subset (window) of elements in an array and slides this window through the array. It's essentially an optimized version of nested loops for subarray problems.

Key Concepts:

Maintains a contiguous subarray (window)
Window can be fixed size or variable size
Slides by adding new elements and removing old ones
Avoids recalculating from scratch for each window

Two Types:

Fixed Window: Window size remains constant (size k)
Variable Window: Window size changes based on conditions

Time Complexity: O(n) - each element added/removed at most once Space Complexity: O(1) - only stores window state

Sliding Window When to Use

Use sliding window when:

Problems involve subarrays or substrings
Looking for longest/shortest subarray with condition
Maximum/minimum sum of subarray
Contains duplicate within k distance
All permutations in string

Keywords to watch for: "subarray", "substring", "window", "contiguous", "k consecutive"

Fixed Window Implementation

/**
 * Template for fixed-size sliding window
 * @param {number[]} arr - Input array
 * @param {number} k - Window size
 */
function fixedWindowTemplate(arr, k) {
  if (arr.length < k) return null;
  
  // Step 1: Build first window
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  
  let result = windowSum; // or whatever you're tracking
  
  // Step 2: Slide window through rest of array
  for (let i = k; i < arr.length; i++) {
    // Remove left element, add right element
    windowSum += arr[i] - arr[i - k];
    result = Math.max(result, windowSum); // Update result
  }
  
  return result;
}

Example: Maximum Sum of Subarray of Size K

/**
 * Find maximum sum of any contiguous subarray of size k
 * @param {number[]} arr - Input array
 * @param {number} k - Window size
 * @return {number} - Maximum sum
 */
function maxSumSubarray(arr, k) {
  if (arr.length < k) return null;
  
  // Calculate sum of first window
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  
  let maxSum = windowSum;
  
  // Slide window through array
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }
  
  return maxSum;
}

// Test
console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9 (5+1+3)

Variable Window Implementation

/**
 * Template for variable-size sliding window
 * @param {number[]} arr - Input array
 */
function variableWindowTemplate(arr, condition) {
  let left = 0;
  let windowState = initialState; // Sum, set, frequency map, etc.
  let result = initialResult;
  
  for (let right = 0; right < arr.length; right++) {
    // Expand window by including arr[right]
    updateWindowState(arr[right]);
    
    // Shrink window while condition is violated
    while (windowInvalid) {
      removeFromWindowState(arr[left]);
      left++;
    }
    
    // Update result with current valid window
    result = updateResult(result, right - left + 1);
  }
  
  return result;
}

Example 1: Longest Subarray with Sum Equals K (Positive Numbers)

/**
 * Find length of longest subarray with sum equal to k
 * @param {number[]} arr - Array of positive numbers
 * @param {number} k - Target sum
 * @return {number} - Maximum length
 */
function longestSubarraySumK(arr, k) {
  let left = 0;
  let sum = 0;
  let maxLen = 0;
  
  for (let right = 0; right < arr.length; right++) {
    // Expand window
    sum += arr[right];
    
    // Shrink window while sum exceeds k
    while (sum > k && left <= right) {
      sum -= arr[left];
      left++;
    }
    
    // Check if we found exact sum
    if (sum === k) {
      maxLen = Math.max(maxLen, right - left + 1);
    }
  }
  
  return maxLen;
}

// Test
console.log(longestSubarraySumK([1, 2, 3, 1, 1, 1, 1, 4, 2], 6)); // 4

Example 2: Longest Substring Without Repeating Characters

/**
 * Find length of longest substring without repeating characters
 * @param {string} s - Input string
 * @return {number} - Maximum length
 */
function lengthOfLongestSubstring(s) {
  let left = 0;
  let maxLen = 0;
  const charSet = new Set();
  
  for (let right = 0; right < s.length; right++) {
    // Shrink window while character already exists
    while (charSet.has(s[right])) {
      charSet.delete(s[left]);
      left++;
    }
    
    // Add current character
    charSet.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

// Test
console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")

Sliding Window Examples

Example 3: Minimum Window Substring

/**
 * Find minimum window in s that contains all characters of t
 * @param {string} s - Source string
 * @param {string} t - Target string
 * @return {string} - Minimum window substring
 */
function minWindow(s, t) {
  if (s.length < t.length) return "";
  
  // Build frequency map of t
  const need = new Map();
  for (let char of t) {
    need.set(char, (need.get(char) || 0) + 1);
  }
  
  let left = 0;
  let minLen = Infinity;
  let minStart = 0;
  let required = need.size; // Number of unique chars needed
  let formed = 0; // Number of unique chars matched
  const windowCounts = new Map();
  
  for (let right = 0; right < s.length; right++) {
    // Expand window
    const char = s[right];
    windowCounts.set(char, (windowCounts.get(char) || 0) + 1);
    
    // Check if frequency matches
    if (need.has(char) && windowCounts.get(char) === need.get(char)) {
      formed++;
    }
    
    // Shrink window while valid
    while (formed === required && left <= right) {
      // Update result
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        minStart = left;
      }
      
      // Remove from left
      const leftChar = s[left];
      windowCounts.set(leftChar, windowCounts.get(leftChar) - 1);
      
      if (need.has(leftChar) && windowCounts.get(leftChar) < need.get(leftChar)) {
        formed--;
      }
      
      left++;
    }
  }
  
  return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
}

// Test
console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"

Pattern 4: Prefix Sum

Prefix Sum Theory

Prefix sum is a preprocessing technique that allows us to answer range sum queries in O(1) time. The idea is to precompute cumulative sums so we don't recalculate them repeatedly.

Key Concepts:

prefix[i] = sum of elements from index 0 to i
Range sum [l, r] = prefix[r] - prefix[l-1]
Trades space (O(n)) for query time (O(1))
Useful when multiple range queries needed

Time Complexity:

Build: O(n)
Query: O(1)

Space Complexity: O(n) for prefix array

Prefix Sum When to Use

Use prefix sum when:

Multiple range sum queries
Subarray sum equals k
Find equilibrium index
Count subarrays with specific sum
2D range sum queries (prefix matrix)

Prefix Sum Implementation

/**
 * Build prefix sum array
 * @param {number[]} arr - Input array
 * @return {number[]} - Prefix sum array
 */
function buildPrefix(arr) {
  const prefix = new Array(arr.length);
  prefix[0] = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    prefix[i] = prefix[i - 1] + arr[i];
  }
  
  return prefix;
}

/**
 * Get sum of elements in range [l, r]
 * @param {number[]} prefix - Prefix sum array
 * @param {number} l - Left index (inclusive)
 * @param {number} r - Right index (inclusive)
 * @return {number} - Sum of range
 */
function rangeSum(prefix, l, r) {
  if (l === 0) return prefix[r];
  return prefix[r] - prefix[l - 1];
}

// Test
const arr = [1, 2, 3, 4, 5];
const prefix = buildPrefix(arr);
console.log(prefix); // [1, 3, 6, 10, 15]
console.log(rangeSum(prefix, 1, 3)); // 9 (2+3+4)

Prefix Sum Examples

Example 1: Range Sum Query - Immutable

/**
 * Class to handle multiple range sum queries efficiently
 */
class NumArray {
  constructor(nums) {
    this.prefix = new Array(nums.length);
    this.prefix[0] = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
      this.prefix[i] = this.prefix[i - 1] + nums[i];
    }
  }
  
  /**
   * Get sum of elements between indices left and right (inclusive)
   * @param {number} left - Left index
   * @param {number} right - Right index
   * @return {number} - Sum of range
   */
  sumRange(left, right) {
    if (left === 0) return this.prefix[right];
    return this.prefix[right] - this.prefix[left - 1];
  }
}

// Test
const numArray = new NumArray([1, 2, 3, 4, 5]);
console.log(numArray.sumRange(0, 2)); // 6
console.log(numArray.sumRange(2, 4)); // 12

Example 2: Find Equilibrium Index

/**
 * Find index where sum of left elements equals sum of right elements
 * @param {number[]} arr - Input array
 * @return {number} - Equilibrium index or -1
 */
function findEquilibriumIndex(arr) {
  const n = arr.length;
  if (n === 0) return -1;
  
  // Build prefix sum
  const prefix = buildPrefix(arr);
  const totalSum = prefix[n - 1];
  
  for (let i = 0; i < n; i++) {
    // Left sum (exclude current)
    const leftSum = i === 0 ? 0 : prefix[i - 1];
    
    // Right sum (exclude current)
    const rightSum = totalSum - prefix[i];
    
    if (leftSum === rightSum) {
      return i;
    }
  }
  
  return -1;
}

// Test
console.log(findEquilibriumIndex([1, 3, 5, 2, 2])); // 2 (index 2: left=4, right=4)

Example 3: Subarray Sum Equals K (with Prefix + Hashing)

/**
 * Count number of subarrays with sum equal to k
 * Uses prefix sum with hashing for O(n) solution
 * @param {number[]} arr - Input array
 * @param {number} k - Target sum
 * @return {number} - Count of subarrays
 */
function subarraySumEqualsK(arr, k) {
  const prefixSumCount = new Map();
  prefixSumCount.set(0, 1); // Base case: empty subarray
  
  let sum = 0;
  let count = 0;
  
  for (let num of arr) {
    sum += num;
    
    // Check if (sum - k) exists
    // If it does, we found subarray(s) with sum k
    if (prefixSumCount.has(sum - k)) {
      count += prefixSumCount.get(sum - k);
    }
    
    // Add current prefix sum to map
    prefixSumCount.set(sum, (prefixSumCount.get(sum) || 0) + 1);
  }
  
  return count;
}

// Test
console.log(subarraySumEqualsK([1, 2, 3, -3, 1, 1, 1, 4, 2], 3)); // 8

Pattern 5: Kadane's Algorithm

Kadanes Theory

Kadane's algorithm finds the maximum sum of a contiguous subarray in O(n) time. It's a dynamic programming approach that decides at each position whether to extend the current subarray or start a new one.

Key Insight: At each position, the maximum subarray ending at that position is either:

The element itself (start new subarray)
The element + maximum subarray ending at previous position (extend)

Formula: current = max(arr[i], current + arr[i])

Time Complexity: O(n) - single pass Space Complexity: O(1) - only need two variables

Kadanes When to Use

Use Kadane's algorithm when:

Finding maximum sum subarray
Finding maximum product subarray (with modification)
Finding maximum circular subarray sum
Buy/sell stock problems (variation)

Kadanes Implementation

/**
 * Find maximum sum of any contiguous subarray
 * @param {number[]} arr - Input array
 * @return {number} - Maximum subarray sum
 */
function maxSubarraySum(arr) {
  if (arr.length === 0) return 0;
  
  let current = arr[0]; // Max sum ending at current position
  let maxSum = arr[0];  // Global maximum
  
  for (let i = 1; i < arr.length; i++) {
    // Either extend current subarray or start new
    current = Math.max(arr[i], current + arr[i]);
    
    // Update global maximum
    maxSum = Math.max(maxSum, current);
  }
  
  return maxSum;
}

// Test
console.log(maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6 ([4,-1,2,1])

Kadanes Examples

Example 1: Maximum Subarray with Indices

/**
 * Find maximum sum subarray and return sum with start/end indices
 * @param {number[]} arr - Input array
 * @return {object} - Object with sum, start, and end indices
 */
function maxSubarrayWithIndices(arr) {
  if (arr.length === 0) return { sum: 0, start: -1, end: -1 };
  
  let current = arr[0];
  let maxSum = arr[0];
  let start = 0;
  let end = 0;
  let tempStart = 0;
  
  for (let i = 1; i < arr.length; i++) {
    // Start new subarray
    if (arr[i] > current + arr[i]) {
      current = arr[i];
      tempStart = i;
    } else {
      // Extend current subarray
      current = current + arr[i];
    }
    
    // Update global maximum
    if (current > maxSum) {
      maxSum = current;
      start = tempStart;
      end = i;
    }
  }
  
  return { sum: maxSum, start, end };
}

// Test
console.log(maxSubarrayWithIndices([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
// { sum: 6, start: 3, end: 6 }

Example 2: Maximum Product Subarray

/**
 * Find maximum product of contiguous subarray
 * Need to track both max and min (negatives can become max)
 * @param {number[]} arr - Input array
 * @return {number} - Maximum product
 */
function maxProductSubarray(arr) {
  if (arr.length === 0) return 0;
  
  let maxProd = arr[0];
  let currentMax = arr[0]; // Max product ending here
  let currentMin = arr[0]; // Min product ending here (for negatives)
  
  for (let i = 1; i < arr.length; i++) {
    const num = arr[i];
    
    // If current number is negative, swap max and min
    if (num < 0) {
      [currentMax, currentMin] = [currentMin, currentMax];
    }
    
    // Update current max and min
    currentMax = Math.max(num, currentMax * num);
    currentMin = Math.min(num, currentMin * num);
    
    // Update global maximum
    maxProd = Math.max(maxProd, currentMax);
  }
  
  return maxProd;
}

// Test
console.log(maxProductSubarray([2, 3, -2, 4])); // 6 ([2,3])
console.log(maxProductSubarray([-2, 3, -4])); // 24 ([-2,3,-4])

Example 3: Maximum Circular Subarray Sum

/**
 * Find maximum sum of circular subarray
 * Either normal max subarray or (total - min subarray)
 * @param {number[]} arr - Input array
 * @return {number} - Maximum circular subarray sum
 */
function maxCircularSubarraySum(arr) {
  if (arr.length === 0) return 0;
  
  // Case 1: Normal max subarray (Kadane's)
  let maxNormal = kadaneMax(arr);
  
  // Case 2: Circular max = total - min subarray
  let total = arr.reduce((sum, num) => sum + num, 0);
  
  // Find min subarray using inverted Kadane's
  let minSubarray = kadaneMin(arr);
  let maxCircular = total - minSubarray;
  
  // Edge case: all negative numbers
  if (maxCircular === 0) return maxNormal;
  
  return Math.max(maxNormal, maxCircular);
}

function kadaneMax(arr) {
  let current = arr[0];
  let maxSum = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    current = Math.max(arr[i], current + arr[i]);
    maxSum = Math.max(maxSum, current);
  }
  
  return maxSum;
}

function kadaneMin(arr) {
  let current = arr[0];
  let minSum = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    current = Math.min(arr[i], current + arr[i]);
    minSum = Math.min(minSum, current);
  }
  
  return minSum;
}

// Test
console.log(maxCircularSubarraySum([5, -3, 5])); // 10 (5 + 5)
console.log(maxCircularSubarraySum([8, -1, 3, 4])); // 15 (8-1+3+4)

Pattern 6: Binary Search on Arrays

Binary Search Theory

Binary search is a divide-and-conquer algorithm that finds an element's position in a sorted array by repeatedly halving the search space. It's one of the most important patterns for reducing time complexity from O(n) to O(log n).

Key Concepts:

Array must be sorted (or have searchable property)
Compares target with middle element
Eliminates half of remaining elements each iteration
Works on any monotonic function

Common Variations:

Find exact value
Find first/last occurrence
Find insertion position
Search in rotated array
Search in 2D matrix

Time Complexity: O(log n) Space Complexity: O(1) iterative, O(log n) recursive

Binary Search When to Use

Use binary search when:

Array is sorted
Looking for a specific value
Finding boundary (first/last occurrence)
Minimizing/maximizing with a constraint
Search space can be divided monotonically

Keywords: "sorted array", "find", "search", "first/last occurrence"

Binary Search Implementation

/**
 * Standard binary search template
 * @param {number[]} arr - Sorted array
 * @param {number} target - Value to find
 * @return {number} - Index of target or -1
 */
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1; // Search right half
    } else {
      right = mid - 1; // Search left half
    }
  }
  
  return -1; // Not found
}

// Test
console.log(binarySearch([1, 3, 5, 7, 9, 11], 7)); // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11], 6)); // -1

Binary Search Examples

Example 1: Find First and Last Position

/**
 * Find starting and ending position of target in sorted array
 * @param {number[]} arr - Sorted array (may have duplicates)
 * @param {number} target - Value to find
 * @return {number[]} - [start, end] or [-1, -1]
 */
function searchRange(arr, target) {
  const findFirst = (arr, target) => {
    let left = 0;
    let right = arr.length - 1;
    let result = -1;
    
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      
      if (arr[mid] === target) {
        result = mid;
        right = mid - 1; // Continue searching left
      } else if (arr[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    
    return result;
  };
  
  const findLast = (arr, target) => {
    let left = 0;
    let right = arr.length - 1;
    let result = -1;
    
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      
      if (arr[mid] === target) {
        result = mid;
        left = mid + 1; // Continue searching right
      } else if (arr[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    
    return result;
  };
  
  const first = findFirst(arr, target);
  if (first === -1) return [-1, -1];
  
  const last = findLast(arr, target);
  return [first, last];
}

// Test
console.log(searchRange([5, 7, 7, 8, 8, 10], 8)); // [3, 4]
console.log(searchRange([5, 7, 7, 8, 8, 10], 6)); // [-1, -1]

Example 2: Search in Rotated Sorted Array

/**
 * Search target in rotated sorted array
 * @param {number[]} arr - Rotated sorted array (distinct values)
 * @param {number} target - Value to find
 * @return {number} - Index or -1
 */
function searchRotated(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) return mid;
    
    // Determine which half is sorted
    if (arr[left] <= arr[mid]) {
      // Left half is sorted
      if (target >= arr[left] && target < arr[mid]) {
        right = mid - 1; // Target in left half
      } else {
        left = mid + 1; // Target in right half
      }
    } else {
      // Right half is sorted
      if (target > arr[mid] && target <= arr[right]) {
        left = mid + 1; // Target in right half
      } else {
        right = mid - 1; // Target in left half
      }
    }
  }
  
  return -1;
}

// Test
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0)); // 4
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 3)); // -1

Example 3: Find Peak Element

/**
 * Find a peak element (greater than neighbors)
 * @param {number[]} arr - Input array
 * @return {number} - Index of peak element
 */
function findPeakElement(arr) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] > arr[mid + 1]) {
      // Peak is in left half (including mid)
      right = mid;
    } else {
      // Peak is in right half
      left = mid + 1;
    }
  }
  
  return left; // or right, they're equal
}

// Test
console.log(findPeakElement([1, 2, 3, 1])); // 2 (element 3)
console.log(findPeakElement([1, 2, 1, 3, 5, 6, 4])); // 5 (element 6)

Example 4: Search 2D Matrix

/**
 * Search for target in 2D matrix
 * Each row is sorted, first element of each row > last of previous
 * @param {number[][]} matrix - 2D matrix
 * @param {number} target - Value to find
 * @return {boolean} - True if found
 */
function searchMatrix(matrix, target) {
  if (matrix.length === 0 || matrix[0].length === 0) return false;
  
  const m = matrix.length;
  const n = matrix[0].length;
  let left = 0;
  let right = m * n - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    // Convert 1D index to 2D coordinates
    const row = Math.floor(mid / n);
    const col = mid % n;
    const midValue = matrix[row][col];
    
    if (midValue === target) {
      return true;
    } else if (midValue < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return false;
}

// Test
const matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
];
console.log(searchMatrix(matrix, 3)); // true
console.log(searchMatrix(matrix, 13)); // false

Pattern 7: Sorting-Based Patterns

Sorting Theory

Many array problems become simpler after sorting. While sorting adds O(n log n) complexity, it can reduce the remaining logic from O(n²) to O(n), resulting in overall better performance.

Key Concepts:

Sorting reveals patterns (duplicates together, ordered pairs)
Enables greedy approaches
Makes binary search possible
Groups related elements

Common Applications:

Merge overlapping intervals
Three sum / four sum problems
Meeting rooms
Remove overlaps
Pair problems

Time Complexity: O(n log n) for sorting + O(n) for logic = O(n log n) Space Complexity: O(1) to O(n) depending on sort algorithm

Sorting When to Use

Use sorting when:

Order doesn't matter in input
Looking for pairs, triplets with conditions
Merging or combining intervals
Detecting overlaps or conflicts
Greedy strategy works on sorted data

Sorting Implementation

/**
 * Basic sorting patterns
 */

// Sort numbers ascending
const arr = [3, 1, 4, 1, 5, 9];
arr.sort((a, b) => a - b);
console.log(arr); // [1, 1, 3, 4, 5, 9]

// Sort numbers descending
arr.sort((a, b) => b - a);
console.log(arr); // [9, 5, 4, 3, 1, 1]

// Sort by custom criteria
const people = [
  { name: 'Alice', age: 30 },
  { name: 'Bob', age: 25 },
  { name: 'Charlie', age: 35 }
];
people.sort((a, b) => a.age - b.age);
console.log(people); // Sorted by age ascending

Sorting Examples

Example 1: Merge Overlapping Intervals

/**
 * Merge all overlapping intervals
 * @param {number[][]} intervals - Array of [start, end] intervals
 * @return {number[][]} - Merged intervals
 */
function mergeIntervals(intervals) {
  if (intervals.length <= 1) return intervals;
  
  // Sort by start time
  intervals.sort((a, b) => a[0] - b[0]);
  
  const result = [];
  result.push(intervals[0]);
  
  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    const current = intervals[i];
    
    // Check if intervals overlap
    if (current[0] <= last[1]) {
      // Merge by extending end time
      last[1] = Math.max(last[1], current[1]);
    } else {
      // No overlap, add as new interval
      result.push(current);
    }
  }
  
  return result;
}

// Test
console.log(mergeIntervals([[1,3], [2,6], [8,10], [15,18]]));
// [[1,6], [8,10], [15,18]]

Example 2: Three Sum

/**
 * Find all unique triplets that sum to zero
 * @param {number[]} arr - Input array
 * @return {number[][]} - Array of triplets
 */
function threeSum(arr) {
  arr.sort((a, b) => a - b); // Sort first
  const result = [];
  
  for (let i = 0; i < arr.length - 2; i++) {
    // Skip duplicates for first number
    if (i > 0 && arr[i] === arr[i - 1]) continue;
    
    // Two pointers for remaining two numbers
    let left = i + 1;
    let right = arr.length - 1;
    const target = -arr[i];
    
    while (left < right) {
      const sum = arr[left] + arr[right];
      
      if (sum === target) {
        result.push([arr[i], arr[left], arr[right]]);
        
        // Skip duplicates for second number
        while (left < right && arr[left] === arr[left + 1]) left++;
        // Skip duplicates for third number
        while (left < right && arr[right] === arr[right - 1]) right--;
        
        left++;
        right--;
      } else if (sum < target) {
        left++;
      } else {
        right--;
      }
    }
  }
  
  return result;
}

// Test
console.log(threeSum([-1, 0, 1, 2, -1, -4]));
// [[-1, -1, 2], [-1, 0, 1]]

Example 3: Meeting Rooms II (Minimum Rooms Required)

/**
 * Find minimum number of meeting rooms required
 * @param {number[][]} intervals - Array of [start, end] meeting times
 * @return {number} - Minimum rooms needed
 */
function minMeetingRooms(intervals) {
  if (intervals.length === 0) return 0;
  
  // Separate and sort start and end times
  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
  const ends = intervals.map(i => i[1]).sort((a, b) => a - b);
  
  let rooms = 0;
  let endPtr = 0;
  
  for (let i = 0; i < starts.length; i++) {
    // If meeting starts before earliest ending, need new room
    if (starts[i] < ends[endPtr]) {
      rooms++;
    } else {
      // Reuse room from ended meeting
      endPtr++;
    }
  }
  
  return rooms;
}

// Test
console.log(minMeetingRooms([[0,30], [5,10], [15,20]])); // 2
console.log(minMeetingRooms([[7,10], [2,4]])); // 1

Example 4: Largest Number from Array

/**
 * Arrange numbers to form largest possible number
 * @param {number[]} nums - Array of non-negative integers
 * @return {string} - Largest number as string
 */
function largestNumber(nums) {
  // Custom comparator: compare concatenations
  nums.sort((a, b) => {
    const order1 = String(a) + String(b);
    const order2 = String(b) + String(a);
    return order2.localeCompare(order1); // Descending order
  });
  
  // Edge case: all zeros
  if (nums[0] === 0) return '0';
  
  return nums.join('');
}

// Test
console.log(largestNumber([10, 2])); // "210"
console.log(largestNumber([3, 30, 34, 5, 9])); // "9534330"

Pattern 8: Hashing with Arrays

Hashing Theory

Hashing uses a hash table (Map or Set in JavaScript) to store and retrieve data in O(1) average time. It's incredibly powerful for tracking frequencies, detecting duplicates, and solving subarray problems.

Key Concepts:

Trade space (O(n)) for time (O(1) lookups)
Map: stores key-value pairs
Set: stores unique values only
Hash tables for frequency counting
Prefix sum + hashing for subarray problems

Time Complexity: O(1) average for insert/lookup, O(n) for building Space Complexity: O(n) for hash table

Hashing When to Use

Use hashing when:

Need fast lookups
Counting frequencies
Detecting duplicates
Two sum / complement problems
Subarray sum equals k
Longest substring problems

Hashing Implementation

/**
 * Common hashing patterns
 */

// Using Map for frequency counting
function frequencyMap(arr) {
  const freq = new Map();
  
  for (let num of arr) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
  
  return freq;
}

// Using Set for unique values
function hasUniqueValues(arr) {
  return new Set(arr).size === arr.length;
}

// Using object as hash table (keys must be strings)
function frequencyObject(arr) {
  const freq = {};
  
  for (let num of arr) {
    freq[num] = (freq[num] || 0) + 1;
  }
  
  return freq;
}

Hashing Examples

Example 1: Two Sum (Unsorted Array)

/**
 * Find two numbers that add up to target
 * @param {number[]} arr - Input array
 * @param {number} target - Target sum
 * @return {number[]} - Indices of two numbers
 */
function twoSum(arr, target) {
  const seen = new Map(); // value -> index
  
  for (let i = 0; i < arr.length; i++) {
    const complement = target - arr[i];
    
    if (seen.has(complement)) {
      return [seen.get(complement), i];
    }
    
    seen.set(arr[i], i);
  }
  
  return [];
}

// Test
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

Example 2: Subarray Sum Equals K

/**
 * Count number of subarrays with sum equal to k
 * Uses prefix sum + hashing
 * @param {number[]} arr - Input array
 * @param {number} k - Target sum
 * @return {number} - Count of subarrays
 */
function subarraySum(arr, k) {
  const prefixSumCount = new Map();
  prefixSumCount.set(0, 1); // Base case
  
  let sum = 0;
  let count = 0;
  
  for (let num of arr) {
    sum += num;
    
    // Check if (sum - k) exists
    if (prefixSumCount.has(sum - k)) {
      count += prefixSumCount.get(sum - k);
    }
    
    // Update frequency of current prefix sum
    prefixSumCount.set(sum, (prefixSumCount.get(sum) || 0) + 1);
  }
  
  return count;
}

// Test
console.log(subarraySum([1, 1, 1], 2)); // 2 ([1,1] appears twice)
console.log(subarraySum([1, 2, 3], 3)); // 2 ([1,2] and [3])

Example 3: Longest Consecutive Sequence

/**
 * Find length of longest consecutive sequence
 * @param {number[]} arr - Input array (unsorted)
 * @return {number} - Length of longest consecutive sequence
 */
function longestConsecutive(arr) {
  const numSet = new Set(arr);
  let maxLen = 0;
  
  for (let num of numSet) {
    // Only start counting if num is start of sequence
    if (!numSet.has(num - 1)) {
      let currentNum = num;
      let currentLen = 1;
      
      // Count consecutive numbers
      while (numSet.has(currentNum + 1)) {
        currentNum++;
        currentLen++;
      }
      
      maxLen = Math.max(maxLen, currentLen);
    }
  }
  
  return maxLen;
}

// Test
console.log(longestConsecutive([100, 4, 200, 1, 3, 2])); // 4 ([1,2,3,4])

Example 4: Top K Frequent Elements

/**
 * Find k most frequent elements
 * @param {number[]} arr - Input array
 * @param {number} k - Number of top elements
 * @return {number[]} - K most frequent elements
 */
function topKFrequent(arr, k) {
  // Build frequency map
  const freq = new Map();
  for (let num of arr) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
  
  // Convert to array and sort by frequency
  const sorted = Array.from(freq.entries())
    .sort((a, b) => b[1] - a[1]);
  
  // Return top k elements
  return sorted.slice(0, k).map(entry => entry[0]);
}

// Test
console.log(topKFrequent([1,1,1,2,2,3], 2)); // [1, 2]

Example 5: Group Anagrams

/**
 * Group anagrams together
 * @param {string[]} strs - Array of strings
 * @return {string[][]} - Grouped anagrams
 */
function groupAnagrams(strs) {
  const groups = new Map();
  
  for (let str of strs) {
    // Sort characters as key
    const sorted = str.split('').sort().join('');
    
    if (!groups.has(sorted)) {
      groups.set(sorted, []);
    }
    
    groups.get(sorted).push(str);
  }
  
  return Array.from(groups.values());
}

// Test
console.log(groupAnagrams(["eat","tea","tan","ate","nat","bat"]));
// [["eat","tea","ate"], ["tan","nat"], ["bat"]]

Pattern 9: In-Place Modification

In-Place Theory

In-place modification means transforming an array using only O(1) extra space. This is important for optimizing space complexity and is often required in technical interviews.

Key Concepts:

Modify array without creating new one
Use existing array space cleverly
Common techniques:
- Swap elements
- Use array values as indices
- Mark visited elements
Usually requires O(1) space

Time Complexity: Varies (often O(n)) Space Complexity: O(1) - only uses a few variables

In-Place When to Use

Use in-place modification when:

Space complexity matters (O(1) required)
Reversing array
Rotating array
Removing elements
Rearranging elements
Array elements can serve as indices

In-Place Implementation

/**
 * Common in-place patterns
 */

// Swap two elements
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

// Reverse array in-place
function reverse(arr) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
  
  return arr;
}

In-Place Examples

Example 1: Rotate Array

/**
 * Rotate array to right by k steps
 * @param {number[]} arr - Input array (modified in-place)
 * @param {number} k - Number of rotations
 */
function rotateArray(arr, k) {
  k = k % arr.length; // Handle k > length
  
  // Reverse entire array
  reverse(arr, 0, arr.length - 1);
  
  // Reverse first k elements
  reverse(arr, 0, k - 1);
  
  // Reverse remaining elements
  reverse(arr, k, arr.length - 1);
  
  return arr;
}

function reverse(arr, start, end) {
  while (start < end) {
    [arr[start], arr[end]] = [arr[end], arr[start]];
    start++;
    end--;
  }
}

// Test
console.log(rotateArray([1, 2, 3, 4, 5, 6, 7], 3)); // [5,6,7,1,2,3,4]

Example 2: Move Zeros to End

/**
 * Move all zeros to end while maintaining order of non-zeros
 * @param {number[]} arr - Input array (modified in-place)
 */
function moveZeroes(arr) {
  let nonZeroPos = 0; // Position for next non-zero
  
  // Move all non-zeros to front
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== 0) {
      arr[nonZeroPos] = arr[i];
      nonZeroPos++;
    }
  }
  
  // Fill remaining with zeros
  for (let i = nonZeroPos; i < arr.length; i++) {
    arr[i] = 0;
  }
  
  return arr;
}

// Alternative: Swap approach
function moveZeroesSwap(arr) {
  let nonZeroPos = 0;
  
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== 0) {
      [arr[i], arr[nonZeroPos]] = [arr[nonZeroPos], arr[i]];
      nonZeroPos++;
    }
  }
  
  return arr;
}

// Test
console.log(moveZeroes([0, 1, 0, 3, 12])); // [1,3,12,0,0]

Example 3: Next Permutation

/**
 * Rearrange array to next lexicographically greater permutation
 * @param {number[]} arr - Input array (modified in-place)
 */
function nextPermutation(arr) {
  let i = arr.length - 2;
  
  // Find first decreasing element from right
  while (i >= 0 && arr[i] >= arr[i + 1]) {
    i--;
  }
  
  if (i >= 0) {
    // Find element just larger than arr[i]
    let j = arr.length - 1;
    while (arr[j] <= arr[i]) {
      j--;
    }
    // Swap
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  
  // Reverse from i+1 to end
  let left = i + 1;
  let right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
  
  return arr;
}

// Test
console.log(nextPermutation([1, 2, 3])); // [1,3,2]
console.log(nextPermutation([3, 2, 1])); // [1,2,3]

Example 4: Product Except Self

/**
 * Return array where output[i] = product of all elements except arr[i]
 * Without using division and in O(1) space (excluding output array)
 * @param {number[]} arr - Input array
 * @return {number[]} - Product array
 */
function productExceptSelf(arr) {
  const n = arr.length;
  const result = new Array(n);
  
  // Left products: result[i] = product of all elements to left
  result[0] = 1;
  for (let i = 1; i < n; i++) {
    result[i] = result[i - 1] * arr[i - 1];
  }
  
  // Right products: multiply by product of all elements to right
  let rightProduct = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= rightProduct;
    rightProduct *= arr[i];
  }
  
  return result;
}

// Test
console.log(productExceptSelf([1, 2, 3, 4])); // [24,12,8,6]

Pattern 10: Cyclic Sort

Cyclic Sort Theory

Cyclic sort is a specialized pattern for arrays containing numbers from 1 to N (or 0 to N-1). It places each number at its correct index by cycling through positions. This pattern is extremely efficient for finding missing/duplicate numbers.

Key Insight: If array contains numbers 1 to N, number i should be at index i-1.

Key Concepts:

Works only when array has numbers in specific range
Places each element at correct position
Cycles until each number is home
Very efficient for missing/duplicate detection

Time Complexity: O(n) - each number moved at most once Space Complexity: O(1) - in-place sorting

Cyclic Sort When to Use

Use cyclic sort when:

Array contains numbers from 1 to N (or 0 to N-1)
Finding missing number
Finding duplicate number
Finding all missing/duplicate numbers
First missing positive number

Keywords: "numbers from 1 to N", "missing", "duplicate", "contains all"

Cyclic Sort Implementation

/**
 * Basic cyclic sort template
 * For array with numbers from 1 to N
 * @param {number[]} arr - Input array (modified in-place)
 */
function cyclicSort(arr) {
  let i = 0;
  
  while (i < arr.length) {
    const correctIndex = arr[i] - 1; // For 1 to N
    
    // If number not at correct position, swap
    if (arr[i] !== arr[correctIndex]) {
      [arr[i], arr[correctIndex]] = [arr[correctIndex], arr[i]];
    } else {
      i++; // Move to next position
    }
  }
  
  return arr;
}

// Test
console.log(cyclicSort([3, 1, 5, 4, 2])); // [1,2,3,4,5]

Cyclic Sort Examples

Example 1: Find Missing Number

/**
 * Find the missing number from 0 to N
 * @param {number[]} arr - Array with N numbers from 0 to N (one missing)
 * @return {number} - Missing number
 */
function findMissingNumber(arr) {
  let i = 0;
  const n = arr.length;
  
  // Cyclic sort (0 to N means arr[i] should be at index arr[i])
  while (i < n) {
    const correctIndex = arr[i];
    
    // Skip if number is N or already at correct position
    if (arr[i] < n && arr[i] !== arr[correctIndex]) {
      [arr[i], arr[correctIndex]] = [arr[correctIndex], arr[i]];
    } else {
      i++;
    }
  }
  
  // Find first index where number doesn't match
  for (let i = 0; i < n; i++) {
    if (arr[i] !== i) {
      return i;
    }
  }
  
  return n; // All numbers present, missing is N
}

// Test
console.log(findMissingNumber([3, 0, 1])); // 2
console.log(findMissingNumber([0, 1])); // 2

Example 2: Find All Duplicates

/**
 * Find all numbers that appear twice
 * Array contains numbers from 1 to N, some appear twice
 * @param {number[]} arr - Input array
 * @return {number[]} - Array of duplicates
 */
function findDuplicates(arr) {
  let i = 0;
  
  // Cyclic sort
  while (i < arr.length) {
    const correctIndex = arr[i] - 1;
    
    if (arr[i] !== arr[correctIndex]) {
      [arr[i], arr[correctIndex]] = [arr[correctIndex], arr[i]];
    } else {
      i++;
    }
  }
  
  // Find duplicates (numbers not at correct index)
  const duplicates = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== i + 1) {
      duplicates.push(arr[i]);
    }
  }
  
  return duplicates;
}

// Test
console.log(findDuplicates([4, 3, 2, 7, 8, 2, 3, 1])); // [2, 3]

Example 3: First Missing Positive

/**
 * Find smallest missing positive integer
 * @param {number[]} arr - Input array (can have negatives, zeros)
 * @return {number} - First missing positive
 */
function firstMissingPositive(arr) {
  let i = 0;
  const n = arr.length;
  
  // Cyclic sort (ignore negatives and numbers > n)
  while (i < n) {
    const correctIndex = arr[i] - 1;
    
    // Only sort positive numbers that fit in range
    if (arr[i] > 0 && arr[i] <= n && arr[i] !== arr[correctIndex]) {
      [arr[i], arr[correctIndex]] = [arr[correctIndex], arr[i]];
    } else {
      i++;
    }
  }
  
  // Find first missing positive
  for (let i = 0; i < n; i++) {
    if (arr[i] !== i + 1) {
      return i + 1;
    }
  }
  
  return n + 1; // All 1 to N present
}

// Test
console.log(firstMissingPositive([1, 2, 0])); // 3
console.log(firstMissingPositive([3, 4, -1, 1])); // 2
console.log(firstMissingPositive([7, 8, 9, 11, 12])); // 1

Example 4: Find All Missing Numbers

/**
 * Find all numbers from 1 to N that don't appear in array
 * @param {number[]} arr - Array of N numbers from 1 to N (some missing)
 * @return {number[]} - Array of missing numbers
 */
function findDisappearedNumbers(arr) {
  let i = 0;
  
  // Cyclic sort
  while (i < arr.length) {
    const correctIndex = arr[i] - 1;
    
    if (arr[i] !== arr[correctIndex]) {
      [arr[i], arr[correctIndex]] = [arr[correctIndex], arr[i]];
    } else {
      i++;
    }
  }
  
  // Find missing numbers
  const missing = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== i + 1) {
      missing.push(i + 1);
    }
  }
  
  return missing;
}

// Test
console.log(findDisappearedNumbers([4, 3, 2, 7, 8, 2, 3, 1])); // [5, 6]

carefree-ladka/DSA in JavaScript.mdx

Mastering Array Patterns for Technical Interviews

Table of Contents

Introduction

Pattern 1: Traversal

Traversal Theory

Traversal When to Use

Traversal Implementation

Traversal Examples

Pattern 2: Two Pointers

Two Pointers Theory

Two Pointers When to Use

Two Pointers Implementation

Two Pointers Examples

Pattern 3: Sliding Window

Sliding Window Theory

Sliding Window When to Use

Fixed Window Implementation

Variable Window Implementation

Sliding Window Examples

Pattern 4: Prefix Sum

Prefix Sum Theory

Prefix Sum When to Use

Prefix Sum Implementation

Prefix Sum Examples

Pattern 5: Kadane's Algorithm

Kadanes Theory

Kadanes When to Use

Kadanes Implementation

Kadanes Examples

Pattern 6: Binary Search on Arrays

Binary Search Theory

Binary Search When to Use

Binary Search Implementation

Binary Search Examples

Pattern 7: Sorting-Based Patterns

Sorting Theory

Sorting When to Use

Sorting Implementation

Sorting Examples

Pattern 8: Hashing with Arrays

Hashing Theory

Hashing When to Use

Hashing Implementation

Hashing Examples

Pattern 9: In-Place Modification

In-Place Theory

In-Place When to Use

In-Place Implementation

In-Place Examples

Pattern 10: Cyclic Sort

Cyclic Sort Theory

Cyclic Sort When to Use

Cyclic Sort Implementation

Cyclic Sort Examples