Array

Array Cheat Sheet

Arrays are a fundamental data structure that store elements of the same type in contiguous memory locations. Their simplicity and direct access to elements via indices make them indispensable in coding interviews. Arrays offer a structured way to manage collections of data under a single variable name, but they also have limitations that are important to understand.

Advantages of Arrays

• Quick Access: Arrays provide O(1) access to elements when the index is known, which is far more efficient than sequential traversal required in data structures like linked lists.

• Simplicity: Handling multiple items under a single variable name streamlines data operations and algorithm implementations.

Disadvantages of Arrays

• Fixed Size: Some programming languages implement arrays with a fixed size, which cannot be altered once initialized. To add more elements than the array's capacity, a new array must be created and the existing elements copied, which is an O(n) operation.

• Modification Costs: Inserting or removing elements from any position other than the end of the array requires shifting elements to maintain order, resulting in an O(n) time complexity.

Key Terms

• Subarray: A contiguous segment within an array, such as a range of elements from index i to j. Example: given an array [2, 3, 6, 1, 5, 4], [3, 6, 1] is a subarray while [3, 1, 5] is not a subarray.

• Subsequence: A sequence that can be derived from the array by removing some elements without changing the order of the remaining elements. Example: given an array [2, 3, 6, 1, 5, 4], [3, 1, 5] is a subsequence but [3, 5, 1] is not a subsequence.

Time Complexity of Array Operations

• Access: O(1)

• Search: O(n), improves to O(log n) if the array is sorted and binary search is used.

• Insert: O(n), but O(1) for insertion at the end of a dynamic array.

• Remove: O(n), but O(1) for removal at the end of a dynamic array.

Considerations

• Duplicates: Determine the impact of duplicate elements on the problem at hand.

• Bounds Checking: Always ensure that your array index operations stay within bounds to prevent runtime errors.

• Efficiency: Opt for index-based operations over slicing or concatenating to avoid unnecessary O(n) operations.

Corner Cases to Consider

• Empty arrays, which have no elements.

• Arrays with a single element, which can simplify or trivialize certain problems.

• Arrays with two elements, which often serve as a base case in recursive algorithms.

• Arrays with repeated elements, which can complicate or facilitate certain search and sort operations.

Patterns for Solving Array Problems

• Sliding Window: Effective for contiguous subarray problems, using two pointers that move in the same direction without crossing.

• Two Pointers: A versatile strategy for problems where pointers may cross or operate on separate arrays.

• Traversing from the Right: Starting from the end of the array can be advantageous in certain algorithms.

• Sorting: Pre-sorting an array can simplify many problems, provided that the original order is not required.

• Precomputation: Techniques like prefix sums or hashing can optimize subarray calculations.

• Index as a Hash Key: Leveraging the array's indices as a hash table can save space and improve efficiency.

• Multiple Traversals: Iterating through the array multiple times is still considered O(n) and can be strategically useful.

Practice Problems

Link	Difficulty
Contains Duplicate	Easy
Best Time to Buy and Sell Stock	Easy
Maximum Subarray	Easy
Maximum Average Subarray I	Easy
Remove Duplicates from Sorted Array	Easy
Merge Sorted Array	Easy
Plus One	Easy
Single Number	Easy
Squares of a Sorted Array	Easy
Remove Element	Easy
Two Sum	Easy
Missing Number	Easy
Two Sum II - Input Array Is Sorted	Medium
Sort Colors	Medium
Find All Duplicates in an Array	Medium
Product of Array Except Self	Medium
Kth Largest Element in an Array	Medium
Minimum Size Subarray Sum	Medium
Fruit Into Baskets	Medium
Subarray Sum Equals K	Medium
Boats to Save People	Medium
3Sum	Medium
Combination Sum	Medium
Merge Intervals	Medium
Container With Most Water	Medium

Arrays Implementation in Programming Languages

Programming languages have different implementations for arrays and their dynamic counterparts, each with unique features.

Golang: Array and Slice (Dynamic Array)

var arr [5]int // Fixed-size array
slice := make([]int, 0) // Dynamic slice

In Golang, arrays are fixed in size, while slices provide a dynamic and flexible alternative built on top of arrays.

Java: Array and ArrayList

int[] arr = new int[5]; // Fixed-size array
ArrayList<Integer> arrayList = new ArrayList<>(); // Dynamic array

Java offers fixed-size arrays and dynamic arrays through the ArrayList class, part of the Collections Framework.

C++: Array and Vector

int arr[5]; // Fixed-size array
std::vector<int> vec; // Dynamic array (Vector)

C++ provides fixed-size arrays and dynamic arrays with the Vector class from the Standard Template Library (STL).

Python: List

arr = [] # Dynamic list (array)

Python's list is inherently dynamic, allowing for flexible array size adjustments.This comprehensive chapter on arrays equips you with the knowledge and strategies needed to tackle array-related problems in coding interviews, highlighting the importance of understanding both the theoretical and practical aspects of arrays across different programming languages.