Make delicious recipes!

Patterns to remember for Arrays


It is clearly difficult to remember so many different ways of solving problems. So we provide a summary of some common ways to solve the above problems. These summarized notes can act like powershots before an exam or an interview. They help to refresh your memory without reading all the questions yet once again.
(Offcourse, you must have practiced or read all the questions almost twice in the past before these powershots start becoming effective).


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.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal