Array Theory

An array is a collection of items stored at contiguous memory locations. The array elements can be accessed using an index. The index of the first element of the array is 0, the index of the second element is 1, and so on.

Experiment: 

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;

int main() {
    int arr[2][3] = {
        {1, 2, 3},
        {4, 5, 6}
    };
    cout << &arr[0][0] << " " << &arr[0][1] << " " << &arr[0][2] << endl;
    cout << &arr[1][0] << " " << &arr[1][1] << " " << &arr[1][2] << endl;
    return 0;
}

When we add or remove an element from an array, the elements are shifted accordingly. This is why adding or removing an element from an array is an O(n) operation.

Given a ==sorted== array arr[] of n ==distinct== elements, write a function to search a given element x in arr[], return -1 if the element is not found.

pseudocode

1
2
3
4
5
6
7
8
9
10

1. Set `l` to 0 and `r` to n-1
2. While `l` is less than or equal to `r`, do steps 3-6
3.      Set `m` to the floor of `(l+r)/2`
4.      If `arr[m]` is equal to `x`, return `m`
5.      If `arr[m]` is less than `x`, set `l` to `m+1`
6.      If `arr[m]` is greater than `x`, set `r` to `m-1`
7. End while
8. Return -1

Notice

  • l and r are the left and right indices of the array.
  • While condition is l <= r because when l is equal to r we still need to check the element at l or r.
  • When calculating (l+2)/2 we can get an overflow if l and r are large. We can use l + (r-l)/2 instead to avoid overflow.
  • As we always set l or r to m+1 or m-1, the loop will eventually terminate.

Complexity

  • Time complexity: O(log n)

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int binarySearch(int arr[], int x) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int middle = left + ((right - left) >> 1);
        if (arr[middle] == x) {
            return middle;
        } else if (arr[middle] < x)  {
            left = middle + 1;
        } else {
            right = middle - 1;
        } 
    }
    return -1;
}

Practice

Learned from practice

  1. Trick: m * n < x is equivlent to m < x / n. This will avoid overflow but we need to be careful with n = 0.

Double Pointer

Given an array and a value, remove all occurrences of that value from the array and return the new length of the array. The elements after the new length do not need to be considered.

idea
Keep two pointers to update the array. Fast pointer iterate the array as normal, while slow pointer record the new array.

Implementation

1
2
3
4
5
6
7
8
9
10
11

int remove(int nums[], int val) {
    int ptr_s = 0;
    for (int ptr_f = 0; ptr_f < nums.size(); ptr_f++) {
        if (nums[ptr_f] != val ) {
            nums[ptr_s++] = val;
        } 
    }
    return ptr_s;
}

Practice

Sliding Window

Given an array with n elements and a value s, you need to return the shortest subarray whose sum is greater or equal to s.

Idea

Sliding window is a essentially updating the start and end position of a subarray until getting the expected result. Usually, the update is done in one iteration and we loop the index of the last position.

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

nt minSubArrayLen(int target, vector<int>& nums) {
    int sum = 0;
    int l = 0;
    int res = 0;
    for (int r = 0; r < nums.size(); r++) {
        sum += nums[r];
        while (sum - nums[l] >= target) {
            sum -= nums[l++];
        }
        if (sum >= target && (res == 0 || res > (r - l + 1))) {
            res = r - l + 1;
        }
    }
    return res;
}

Practice

Simulation

idea
When writing simulation programs, we often define complex loops. For these complex loops, it is important to remember that the rules followed by each loop remain unchanged. Additionally, it is a good approach to extract the functionality that can be reused from the complex program.

Practice

K Sum

Find K distinct values in a given array that add up to a target value.

idea
Sort the array first, then use a brute force loop to iterate over the K-2 values. Use double pointers to search for the last two values in O(N) complexity. The total complexity will be $O(N^{K-1})$.

The idea behind using double pointers to search for two values in a sorted array is as follows:

1
2
3
4
5
6
7
8
9
ptr1 = left_bound; ptr2 = right_bound;
if arr[ptr1] + arr[ptr2] < target:
    ptr1++;  // increase lower bound
if arr[ptr1] + arr[ptr2] > target:
    ptr2--;  // decrease upper bound
if arr[ptr1] + arr[ptr2] == target:
    add [ptr1, ptr2] to the result
    move ptr1 and ptr2 towards the center until they point to different values
repeat steps 2-8 until ptr1 >= ptr2

Practice
Leetcode 15 - 3Sum
Leetcode 18 - 4Sum