Data Structures and Algorithms

Last Modified: 2/12/2025

1 Data Structures and Algorithms Overview

1.1 Mathematical Models

Cost Models: Use some basic operations as a proxy for running time.

Operation	Frequency
Variable Declaration	$N + 2$
Assignment Statement	$N + 2$
Less than Compare	$\frac{\left(N + 1\right)\left(N + 2\right)}{2}$
Equal to Compare	$\frac{N\left(N - 1\right)}{2}$
Array Access	$N\left(N - 1\right)$
Increment	$\frac{N\left(N - 1\right)}{2}$ to $N\left(N - 1\right)$

Key Notes:

Estimate running time (or memory) as a function of input size $N$
Ignore lower order terms
- When $N$ is large, terms are negligible.
- When $N$ is small, we don’t care.

1.2 Order-of-Growth Classifications

1.2.1 Common Classifications

Order of Growth	Name	Typical Code Framework	Description	Example	$T\left(2N\right)/T\left(N\right)$
$1$	Constant	`a = b + c;`	Statement	Add two numbers	$1$
$\log N$	Logarithmic	`while (N > 1) N /= 2;`	Divide in half	Binary search	$-1$
$N$	Linear	`for (int i = 0; i < N; i++) {...}`	Loop	Find the maximum	$2$
$N \log N$	Linearithmatic	See mergesort lecture	Divide and conquer	Mergesort	$-2$
$N^2$	Quadratic	`for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {...}`	Double loop	Check all pairs	$4$
$N^3$	Cubic	`for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) {...}`	Triple loop	Check all triples	$8$
$2^N$	Exponential	See combinatorial search lecture	Exhaustive search	Check all subsets	$T\left(N\right)$

1.2.2 Binary Search

Procedure: Compare key against middle entry

Too small, go left.
Too big, go right.
Equal, found!

Property: Binary search uses $1 + \log N$ to search in a sorted array of size $N$ .

Proof:

T(N) = \text{number of compares to binary search in a sorted array of size} \leq N

\begin{align*} T\left(N\right) &\leq T\left(\frac{N}{2}\right) + 1 \\ &\leq T\left(\frac{N}{4}\right) + 1 + 1\\ &\leq T\left(\frac{N}{8}\right) + 1 + 1 + 1 \\ &\vdots \\ &\leq T\left(\frac{N}{N}\right) + 1 + 1 + 1 + \cdots + 1 \\ &\leq 1 + \log N \end{align*}


15 collapsed lines
1
public static int binarySearch(int[] a, int key) {
2
    int lo = 0;
3
    int hi = a.length - 1;
4
    while (lo <= hi) {
5
        int mid = lo + (hi - lo) / 2;
6
        if (key < a[mid]) {
7
            hi = mid - 1;
8
        } else if (key > a[mid]) {
9
            lo = mid + 1;
10
        } else {
11
            return mid;
12
        }
13
    }
14
    return -1;
15
}


17 collapsed lines
1
#include <vector>
2

3
int binarySearch(std::vector<int> arr, int x) {
4
    int l = 0, r = arr.size() - 1;
5
    while (l <= r) {
6
        int m = l + (r - l) / 2;
7
        if (arr[m] == x) {
8
            return m;
9
        }
10
        if (arr[m] < x) {
11
            l = m + 1;
12
        } else {
13
            r = m - 1;
14
        }
15
    }
16
    return -1;
17
}


11 collapsed lines
1
def binary_search(arr, x):
2
    l, r = 0, len(arr) - 1
3
    while l <= r:
4
        m = l + (r - l) // 2
5
        if arr[m] == x:
6
            return m
7
        if arr[m] < x:
8
            l = m + 1
9
        else:
10
            r = m - 1
11
    return -1

1.2.3 3-Sum

LeetCode 15: 3Sum

Description: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k , and nums[i] + nums[j] + nums[k] == 0.

Procedure

Sort $N$ (distinct) numbers => $O\left(N \log N\right)$
Binary Search for each pair $-\left(a_i + a_j\right)$ => $O(N^2 \log N)$

Better algorithm: Sorting & Two pointers => $O\left(N^2\right)$


46 collapsed lines
1
import java.util.ArrayList;
2
import java.util.Arrays;
3
import java.util.List;
4

5
public class Solution {
6
    public Solution() {
7
    }
8

9
    public List<List<Integer>> threeSum(int[] nums) {
10
        int n = nums.length;
11
        Arrays.sort(nums);
12
        List<List<Integer>> answers = new ArrayList<>();
13

14
        for (int first = 0; first < n; ++first) {
15

16
            if (first > 0 && nums[first] == nums[first - 1]) {
17
                continue;
18
            }
19

20
            int third = n - 1;
21
            int target = -nums[first];
22

23
            for (int second = first + 1; second < n; second++) {
24
                if (second > first + 1 && nums[second] == nums[second - 1]) {
25
                    continue;
26
                }
27

28
                while (second < third && nums[second] + nums[third] > target) {
29
                    --third;
30
                }
31
                if (second == third) {
32
                    break;
33
                }
34

35
                if (nums[second] + nums[third] == target) {
36
                    List<Integer> list = new ArrayList<>();
37
                    list.add(nums[first]);
38
                    list.add(nums[second]);
39
                    list.add(nums[third]);
40
                    answers.add(list);
41
                }
42
            }
43
        }
44
        return answers;
45
    }
46
}


37 collapsed lines
1
#include <vector>
2
#include <algorithm>
3

4
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
5
    const int n = static_cast<int>(nums.size());
6
    std::sort(nums.begin(), nums.end());
7

8
    std::vector<std::vector<int>> answer;
9

10
    for (int first = 0; first < n; first++) {
11

12
        if (first > 0 && nums[first] == nums[first - 1]) {
13
            continue;
14
        }
15

16
        int third = n - 1;
17
        const int target = -nums[first];
18

19
        for (int second = first + 1; second < n; second++) {
20
            if (second > first + 1 && nums[second] == nums[second - 1]) {
21
                continue;
22
            }
23

24
            while (second < third && nums[second] + nums[third] > target) {
25
                --third;
26
            }
27
            if (second == third) {
28
                break;
29
            }
30

31
            if (nums[second] + nums[third] == target) {
32
                answer.emplace_back(std::vector<int>{nums[first], nums[second], nums[third]});
33
            }
34
        }
35
    }
36
    return answer;
37
}


28 collapsed lines
1
from typing import List
2

3

4
def threeSum(nums: List[int]) -> List[List[int]]:
5
    n = len(nums)
6
    nums.sort()
7
    ans = list()
8

9
    for first in range(n):
10

11
        if first > 0 and nums[first] == nums[first - 1]:
12
            continue
13
        third = n - 1
14
        target = -nums[first]
15

16
        for second in range(first + 1, n):
17
            if second > first + 1 and nums[second] == nums[second - 1]:
18
                continue
19

20
            while second < third and nums[second] + nums[third] > target:
21
                third -= 1
22
            if second == third:
23
                break
24

25
            if nums[second] + nums[third] == target:
26
                ans.append([nums[first], nums[second], nums[third]])
27

28
    return ans