Arrays and Hashing

Most complex data structures are built from simpler ones. At the very bottom, you’ll almost always find the array. It’s a fundamental way to organize data in a computer’s memory, and mastering it is non-negotiable for coding interviews.

An array is a collection of items stored in a contiguous block of memory. Think of it as a row of numbered mailboxes. Because each slot has a unique index, you can access any item directly if you know its position. This makes reading from an array incredibly fast, an operation with a time complexity of $O(1)$ .

However, this rigid structure has its downsides. If you want to insert or delete an item in the middle, you have to shift all the subsequent items over, which can be slow. This is why understanding the trade-offs is key.

Array Manipulation Techniques

Solving array-based problems often involves clever manipulation techniques. One of the most common is the two-pointer approach. Instead of using one pointer to iterate through the array, you use two. These pointers can move towards each other, away from each other, or in the same direction at different speeds.

This technique is perfect for tasks like finding pairs that sum to a target, reversing an array, or detecting palindromes. Let's see it in action to check if a string is a palindrome.

def is_palindrome(s):
    left = 0
    right = len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    
    return True

# Example usage
print(is_palindrome("racecar")) # True
print(is_palindrome("hello"))   # False

Here, the left pointer starts at the beginning and the right pointer starts at the end. They move toward the middle, comparing characters along the way. If they ever find a mismatch, we know it's not a palindrome. This avoids nested loops and solves the problem in $O(n)$ time.

Smarter Lookups with Hash Tables

What if you need to quickly check if an item exists in a collection, without caring about its order? Scanning an array takes $O(n)$ time, which is often too slow. This is where hash tables come in.

Hash Table

noun

A data structure that stores key-value pairs. It uses a hash function to compute an index, or 'bucket', from a key, where the corresponding value is stored.

In many programming languages, you'll know this structure by a different name. In Python, it's called a dictionary. In JavaScript, it's an Object or a Map. In Java, it's a HashMap. Whatever the name, the principle is the same.

The magic of hash tables is their speed. On average, adding, removing, and looking up items takes constant time, or $O(1)$ . This is a massive improvement over an array's $O(n)$ search time.

A common pattern in LeetCode problems is to iterate through an array and store elements or their properties (like their index) in a hash table. This allows you to quickly check for duplicates or find pairs of numbers that meet a certain condition. For example, in the famous "Two Sum" problem, you can store each number you've seen and the complement you're looking for. When you find a number that's already in your hash table as a complement, you've found your pair.

Any time a problem statement includes words like "unique," "duplicate," or asks you to find pairs, your first thought should often be: can a hash table help?

By combining the simple storage of arrays with the fast lookups of hash tables, you create a powerful toolkit for solving a huge range of algorithmic challenges. Get comfortable with these two, and you'll have a solid foundation for the tougher problems ahead.

Quiz Questions 1/6

What is the time complexity for accessing an element in an array by its index?

Quiz Questions 2/6

Why can inserting or deleting an element in the middle of an array be a slow operation?

LeetCode Blind 75 Deep Dive

LeetCode Blind 75 Deep Dive

Arrays and Hashing