# Arrays

Array problems are by far the most common type of algorithm problems I have encountered. There are a few techniques that are used very commonly so it is best to familiarize yourself with all of them

## Runtime analysis

Insert

Start/End: $O(1)$

Middle: $O(n)$

Search

Sorted (binary search): $O(\log n)$

Unsorted (linear search): $O(n)$

Delete: similar to insert

Access: $O(1)$

## Corner cases

Empty array

Array of size 1 or 2

Monotonically increasing/decreasing

Duplicate values

Consecutive repeated elements

Odd number of elements

## Take note…

Index out of bounds, check with: $0 \leq |x| < len(arr)$

Handling duplicate entries

Is the array sorted?

If so, can you use Binary Searchinstead?

If not, can you sort it while preserving information?

Do not over-concatenate

Use

`append`

and then copy the accumulation using`acc[::]`

to reduce the amount of concatenation, refer to Recursionfor more information on this technique

Relationship between elements in an array such as the information that can be gathered based on the values/indices of the elements

## Techniques

### Sorting first

This depends entirely on whether or not the information in the array can be preserved after sorting (take note of the effects of stable vs unstable sorting).

If the array can be sorted first, Binary Searchcould be applied afterwards

Useful when finding the minimum difference between all elements and finding the lowest possible running total using prefix sums (commonly found in subsequence problems)

If the array cannot be sorted without losing information, then try other solutions

### Two pointers

Pointers that point to different/same points in the array and move (often) independently of one another

Can be used to traverse across two arrays simultaneously

Pointers can cross one another

Commonly used for problems that involve palindromes

When solving two pointer problems, focus on realizing the following conditions (similar to Binary Search):

When to move the left pointer?

When to move the right pointer?

Where to move if neither condition is met?

### Sliding window

Sliding windows are simply two pointers that never cross one another. They can be of a fixed size (useful if the window size is pre-defined) or a flexible size (resizing depending on conditions)

To understand how the window moves, first answer the following questions:

Is the window fixed?

When to expand right?

When to retract left? (some problems don't require retracting the left at all)

What does each window represent?

What to do when an element enters/leaves the window?

Sliding window problems are often paired with frequency arrays like Longest Substring Without Repeating Character

There are two categories of problem that can be solved using sliding windows, namely:

#### Maximizing problems

The sliding window never shrinks, meaning that it is only extending by one or shifting by one, such as in Maximum Product Subarray

The final answer is usually the size of the sliding window since the starting position or contents of the window does not matter

#### Minimizing problems

The sliding window retracts until the window no longer satisfies a given condition, such as Minimum Window Substring

The size of the window should be tracked after each retraction and that represents the final answer

### Reverse traversal

Rather than traversing from left to right, try traversing from right to left and see if new information can be gathered instead

Try combining both normal and reverse traversal together to see if the problem can be solved that way

### Prefix/Suffix sums

Often used to reduce repeated computation that requires the prefix/suffix of the array

Not limited to the sum, product and other properties are possible as well

May require both sums so try that out as well

If both are required, there's a chance that the one of the arrays can be converted to an accumulating variable that is computed to save both time and space

Pay extra attention to whether or not the prefix should include the value at

`i`

### Using index as key/Treating indices as buckets

Sometimes, you can visualize the array as a set of buckets where the index corresponds to a key/bucket and allows you to use this information to perform computation. This pattern is quite hard to spot so I have included some questions you can try to develop the intuition for

Each index represents an element in the array relative to that position (like index 0 is supposed to be element 1)

Algorithms like cyclic sorting use this assumption

Common manipulations: negate the value in the cell to indicate that the value is present in some other part of the array or adding the

`MAX + 1`

to those values

Practice questions:

First Missing Positive

Find the Duplicate Number

Missing Number

### Kadane's algorithm

This is a relatively niche algorithm used in problems like Maximum Product Subarray and Maximum Subarray. However, it can still be generalized to solve other problems

Focus on understanding how the accumulation of values can be generalized across elements

Often involves tracking a local value (running variable) and global value (final result)

Update the global value after every iteration to avoid missing the last element

### Divide and conquer

Divide the existing array into two/`N`

parts and perform simpler work on each part. This technique is the corner stone of merge sort

### Iteration patterns

Iterate over one array while moving the other with a pointer

Jumping around the array given the current value

Last updated