Patterns to remember for Arrays - PrismoSkills

Patterns to remember for Arrays - PrismoSkills

Arrays can be transformed in several ways.
Remember these common transforms whenever finding solutions:

1. Sort the array.
   Sorting an array can simplify many problems.
   Array becomes eligible for O(log N) search which is very efficient.
   Most good algorithms sort in O(N log N) time but if range of input is known, Counting Sort can do it in O(N) time.
   Flash-Sort also provides close to O(N) performance for sorting.
   
   
2. Create MinimumInLeft and MaximumInRight arrays.
   Moving from left to right, create MinimumInLeft array which stores minimum element seen so far.
   Similarly, moving from right to left, create MaximumInRight which stores maximum seen so far.
   These arrays can be used to find:
   1. Two elements with maximum difference.
   2. Two elements with maximum distance.
   Complexity: O(n)
   
   
3. Use Increasing Stack
   Create a stack and traverse the array from left to right.
   Current element in the array goes onto the stack only if its larger than the number already on top of the stack.
   If current element is smaller than the stack top, pop stack elements until stack's top becomes smaller than the current number.
   This stack gives us the left-number immediately lower than a given number in the array.
   Complexity: O(n)
   
   
4. Use Decreasing Stack
   Create a stack and traverse the array from left to right.
   Current element in the array goes onto the stack only if its smaller than the number already on top of the stack.
   If current element is larger than the stack top, pop stack elements until stack's top becomes larger than the current number.
   This stack gives us the right-number immediately larger than a given number in the array.
   Complexity: O(n)
   
   
5. Create LeftPattern and RightPattern arrays.
   This is a generalization of #2 above.
   When an operation involves analyzing trends on left and right side of each array element, then think about creating the above arrays. One array can be used to hold results for left-side computation for each element and other can be used to hold results for right-side computation for each element. When the two arrays have been formed, iterate simultaneously on them to compare corresponding elements in these helper arrays.
   Complexity: O(n) Example:
   1. Create LeftPattern holding length of largest increasing left sub-array ending at current element.
   2. Create RightPattern holding length of largest decreasing right sub-array ending at current element.

Read full article from Patterns to remember for Arrays - PrismoSkills