Array

Sp

Technique 1: Double reverse

This technique can be applied to problems like array rotation, and reverse words in string.

Remember that the rotation number might exceeds the size of the arry.

• Rotate Array

Technique 2: Selection Sort

We normally use two pointers: one pointing at the start of the second half, one pointing at the currect processing position.

We can also use the index of the last element of the sorted half, but then we need to plus 1 to the index before swapping.

• Selection sort
• Remove Element in Place
• Remove Duplicates From Sorted Array

Technique 3: Find the second largest and so on.

Sometimes we may not only need to find the largest number in the array, but also the second, third largest. This algorithm can be applied to problmes like:

• Maximum Product of Three Number
• Third Maximum Number
• Largest Number At Least Twice of O

Technique 4: Using stack to check balance

Stack will provide a reverse order to help check element backwards.

• Balance parentheses
• Majority element in array (need to verify candidate).

Technique 5: Using hash map

We can use hash map to simplify searching for certain element in array in constant time.

• Two Sum

Technique 6: Moore’s Voting Algorithmt

The Boyer–Moore majority vote algorithm is an algorithm for finding the majority of a sequence of elements using linear time and constant space.

Note: We need a counter store the occurences of the candidate.

1. Initialize an element m and a counter i with i = 0
2. For each element x of the input sequence: If i = 0, then assign m = x and i = 1 else if m = x, then assign i = i + 1 else assign i = i − 1
3. Return m

Even if the major item doesn't exist in the array, this algorith will still output a candidate. Therefore if we can't guarantee the major element exist, we need a second iteration to check if the candidate is actually the major element.

Technique 5: Sliding window

We use two int to mark the start and end of the array, and modify the them according the required condition.

• Longest Continuous Increasing Subsequence

Technique 6: Merge Sorted Arrays In Place

The idea is to move larger elements to array2.

1. We begin from last element of arr2 and search it in arr1.
2. If there is a greater element in arr1, then we move last element of arr1 to arr2.
3. To keep arr1 and arr2 sorted, we need to place last element of arr2 at correct place in arr1.
4. We can use Insertion Sort type of insertion for this.

Technique 7: Store additional information inside the array

We can store additional information right into the array without using extra space.

This technique is used in problems like:

• Max Area of Island
• Find All Numbers Disappeared in an Array
• Find All Duplicates in an Array

Technique 8 : Maximum difference between two elements

To find the max difference between two elements in the array, we can keep track of the min element we found so far.

In the loop, we keep track of two things

1. Maximum difference found so far.

2. Min number visited so far.

3. Best Time to Buy and Sell Stock

Technique 9 : Peak Valley Approach

Find the peak and valley in array.

• Best Time to Buy and Sell Stock II

Technique 10 : Kadane’s Algorithm

Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this).

Initialize:
    max_so_far = INT_MIN
    max_ending_here = 0

Loop for each element of the array:
  (a) max_ending_here = max_ending_here + a[i]
  (c) max_so_far = max(max_so_far, max_ending_here)
  (b) max_ending_here = max(0, max_ending_here)
return max_so_far

• Maximum Subarray Sum

Technique 11: Saving indexes of all element

The idea of this technique is to save the indexes of each element value, and use it latter

• Degree of Array

Technique 12: XOR

If we take XOR of zero and some bit, it will return that bit

* a XOR 0 = a

If we take XOR of two same bits, it will return 0

* a XOR a = 0

a XOR b XOR a = (a XOR a) XOR b = 0 XOR b = b

• Single Number

Technique 13: create all the permutations of numbers from 1 to N

Sometime we need to check all permutations of the array in order to find our answer.

1. First we need to create a visited array to check if the item has been visited.
2. We loop through the entire range from 1 to N, this represents the current item.
3. We use a variable called pos to represent the current position.

4. Every time we found an item that satisfy the requirement, we mark it as visited, and move on to the next item.

5. Beautiful Arrangement

Technique 14:

To always access the middle element

for (int i=0; i<(size+1)/2; i++)
// instead of 
for (int i=0; i<=size/2; i++)

• Flipping an Image