Interview Cheat Sheets | Array Cheat Sheet

December 20th, 2023

Introduction

This article will serve to further summarize the excellent overview of arrays from the tech interview handbook.

Advantages and Disadvantages of Arrays

1. Advantages:
   • Stores multiple elements with a single variable name.
   • Fast access with the index.
2. Disadvantages:
   • Slow addition/removal in the middle.
   • Fixed size in certain languages requires reallocation for size changes.

Common Terms and Time Complexity

This section introduces common terms related to arrays and delves into the time complexity of various operations, including access, search, insertion, and removal.

Common Terms

1. Terms:
   • Subarray: Contiguous range of values within an array.
   • Subsequence: Sequence derived by deleting elements without changing order.

Time Complexity

Interview Considerations

1. Things to Look Out For:
   • Clarify the handling of duplicate values.
   • Avoiding index out-of-bounds errors.
   • Be cautious about slicing and concatenating arrays.

Techniques for Array Problems

This section presents essential techniques for addressing array problems, including sliding windows, two pointers, traversing from the right, sorting, pre-computation, and indexing as a hash key.

Techniques

1. Sliding Window:

   • A technique used to efficiently solve problems related to subarrays or subsequences.
   • Involves maintaining a “window” of elements within the array and sliding this window through the array to find the desired result.
   • The key idea is to optimize the process of checking different subarrays by avoiding unnecessary re-computation.

   Here are the main steps involved in the sliding window algorithm:

   1. Define the Window: Determine the size and starting position of the window. The window is essentially a subarray or subsequence within the given array.

   2. Initialize Pointers: Initialize two pointers, typically at the beginning of the array. One pointer (usually the left one) represents the start of the window, and the other (usually the right one) represents the end of the window.

   3. Expand the Window: Move the right pointer to the right, expanding the window. Check if the current window satisfies the problem’s constraints or requirements.

   4. Contract the Window: If the current window violates the problem constraints, move the left pointer to the right, contracting the window. Continue this process until the window again satisfies the constraints.

   5. Update Result: Keep track of the result or perform any necessary operations on the current window.

   6. Repeat: Continue steps 3-5 until the right pointer reaches the end of the array.

   The sliding window technique is particularly useful for solving problems that involve finding the maximum or minimum sum/subarray, checking for a particular pattern, or optimizing a function over a subarray. It’s efficient because it avoids redundant computations by reusing information from the previous window.

   Let’s look at a simple example to illustrate the sliding window algorithm:

   Example: Maximum Sum Subarray of Size K

   Given an array of integers and an integer k, find the maximum sum of a subarray of size k.

   function maxSumSubarray(arr: number[], k: number): number {
     const n: number = arr.length;
   
     // Calculate the initial window sum
     let windowSum: number = arr.slice(0, k).reduce((sum, num) => sum + num, 0);
     let maxSum: number = windowSum;
   
     // Slide the window to the right and update the sums
     for (let i = k; i < n; i++) {
       windowSum = windowSum - arr[i - k] + arr[i];
       maxSum = Math.max(maxSum, windowSum);
     }
   
     return maxSum;
   }
   
   // Example usage
   const arr: number[] = [1, 4, 2, 10, 2, 3, 1, 0, 20];
   const k: number = 4;
   const result: number = maxSumSubarray(arr, k);
   console.log(result); // Output: 24
   

   In this example, the window size is k, and we initialize the window sum with the sum of the first k elements. We then slide the window to the right, updating the window sum by subtracting the element that goes out of the window and adding the new element coming into the window. We keep track of the maximum sum encountered during the process.

   This approach has a time complexity of O(n) since each element is processed exactly once.

2. Two Pointers:

   • A technique used to solve problems that involve searching for a pair or a subarray satisfying certain conditions.
   • Maintains two pointers that traverse the array or sequence in a specific way, allowing for efficient exploration of elements.
   • Generalizing sliding window with pointers that can cross.
   • Examples: Sort Colors, Palindromic Substrings.

   Here are the main concepts and steps involved in the Two Pointers algorithm:

   1. Initialization: Initialize two pointers, often named left and right, at different ends of the array or sequence.

   2. Pointer Movement: Move the pointers based on the problem requirements. Common strategies include:

   • Moving both pointers towards each other.

   • Moving only one pointer while keeping the other fixed.

   • Moving both pointers in the same direction.

   1. Condition Checking: At each step, check if the current configuration of pointers satisfies the given conditions or constraints. Adjust the pointers accordingly.

   2. Iterate: Repeat steps 2-3 until the pointers meet or traverse the entire array.

3. Traversing from the Right:

   • Utilizing right-to-left traversal in specific scenarios.
   • Examples: Daily Temperatures, Number of Visible People in a Queue.

4. Sorting the Array:

   • Considering sorted or partially sorted arrays for faster solutions.
   • Examples: Merge Intervals, and non-overlapping Intervals.

5. Precomputation:

   • Using hashing or prefix/suffix sum/product for summation or multiplication.
   • Examples: Product of Array Except Self, Minimum Size Subarray Sum.

6. Index as a Hash Key:

   • Utilizing the array itself as a hash table for O(1) space.
   • Examples: First Missing Positive, Daily Temperatures.

7. Traversing the Array More Than Once:

   • Recognizing the efficiency of multiple traversals.
   • Instances where traversing multiple times is beneficial.

Essential Questions

• Two Sum: My solution
• Best Time to Buy and Sell Stock: My solution
• Product of Array Except Self: My solution
• Maximum Subarray: My solution