Arrays and Strings

The Building Blocks: Arrays and Strings

Arrays are one of the most fundamental data structures in programming. Think of an array as a row of numbered mailboxes. Each mailbox holds one piece of information, and its number, called an index, tells you exactly where to find it. This makes accessing any item incredibly fast, as long as you know its index. The first mailbox is usually at index 0, not 1.

This structure has a few key properties:

Ordered Collection: Items are stored in a specific sequence.
Indexed Access: You can grab any element directly using its index, which is an $O(1)$ operation, meaning it takes constant time regardless of the array's size.
Fixed Size (often): In many languages, you have to decide the size of an array when you create it, and it can't be changed later without creating a new one.

While getting an item is fast, adding or removing one from the middle can be slow. To insert an item, you have to shift all the subsequent items over to make room. Deleting an item means shifting everything back to fill the gap. These operations can be $O(n)$ , taking time proportional to the number of elements.

Strings are essentially arrays of characters. "Hello" is just an array containing 'H', 'e', 'l', 'l', 'o'. Because of this, they share many properties with arrays. However, a crucial difference in many languages is that strings are immutable. This means once a string is created, it cannot be changed. If you want to add a character, you're actually creating an entirely new string in memory.

The Two Pointers Technique

Now that we understand arrays and strings, let's look at a powerful technique for solving problems with them: the Two Pointers technique. It’s not a data structure itself, but a clever method for iterating through data.

Instead of using one index to loop through an array, we use two. These "pointers" (which are just variables holding array indices) can move in different ways. They might start at opposite ends and move toward each other, start at the same place and move apart, or move in the same direction at different speeds. This approach can often turn a slow, brute-force solution into a much faster one.

The Two Pointers technique is most useful on sorted arrays or for problems involving palindromes.

Let's see it in action. A classic problem is finding if any two numbers in a sorted array add up to a specific target value. The brute-force way is to check every possible pair of numbers. That works, but it's slow, taking $O(n^2)$ time.

With two pointers, we can do it in $O(n)$ time. We place one pointer (left) at the beginning of the array and another (right) at the very end. We add the numbers at these two positions.

Condition	Action
`sum > target`	The sum is too big. We need a smaller number, so we move the `right` pointer one step to the left.
`sum < target`	The sum is too small. We need a larger number, so we move the `left` pointer one step to the right.
`sum == target`	We found our pair!

We repeat this process until the pointers meet or cross, which means we've checked all possibilities without finding a pair.

function hasPairWithSum(array, target) {
  let left = 0;
  let right = array.length - 1;

  while (left < right) {
    const sum = array[left] + array[right];

    if (sum === target) {
      return true; // Found a pair
    } else if (sum > target) {
      right--; // Sum is too high, try a smaller number
    } else {
      left++; // Sum is too low, try a larger number
    }
  }

  return false; // No pair found
}

This technique works for many other problems, too. To check if a string is a palindrome (reads the same forwards and backward, like "racecar"), you can put one pointer at the start and one at the end. Move them toward the middle, checking if the characters they point to are the same. If you find a mismatch, it's not a palindrome. If they meet without any mismatches, it is.

Another common use is removing duplicates from a sorted array. You can use a "slow" pointer to track the position of the last unique element and a "fast" pointer to scan the array. When the fast pointer finds a new, unique element, you copy it to the position after the slow pointer and advance both. This modifies the array in-place, efficiently.

Mastering arrays, strings, and simple but powerful patterns like the Two Pointers technique is a huge step in becoming a better problem solver.

Quiz Questions 1/5

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

Quiz Questions 2/5

In many programming languages, a primary difference between an array of characters and a string is that strings are often immutable.

With these fundamentals, you're ready to tackle a wide range of coding challenges.

LeetCode Mastery

LeetCode Mastery

Arrays and Strings

The Building Blocks: Arrays and Strings

The Two Pointers Technique