Maximum single sell profit from stock

Problem
Suppose we are given an array of n integers representing stock prices on a single day. We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay, such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit.

OR

Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[].


Example
Input = {5        10         4         6        7}
Output = 5,10 => buy at 5 and sell at 7

Solution

Method 1 - Brute force
Clearly there is an O(n²) solution to the algorithm by trying out all possible (buyDay, sellDay) pairs and taking the best out of all of them. However, is there a better algorithm, perhaps one that runs in O(n) time?

int maxDiff(int arr[], int arr_size)
{     
  int max_diff = arr[1] - arr[0];
  int i, j;
  for(i = 0; i < arr_size; i++)
  {
    for(j = i+1; j < arr_size; j++)
    {        
      if(arr[j] - arr[i] > max_diff)   
         max_diff = arr[j] - arr[i];
    }    
  }          
  return max_diff;
}    

Method 2 - Divide and Conquer
If we have a single day, the best option is to buy on that day and then sell it back on the same day for no profit. Otherwise, split the array into two halves. If we think about what the optimal answer might be, it must be in one of three places:

1. The correct buy/sell pair occurs completely within the first half.
2. The correct buy/sell pair occurs completely within the second half.
3. The correct buy/sell pair occurs across both halves - we buy in the first half, then sell in the second half.

We can get the values for (1) and (2) by recursively invoking our algorithm on the first and second halves. For option (3), the way to make the highest profit would be to buy at the lowest point in the first half and sell in the greatest point in the second half. We can find the minimum and maximum values in the two halves by just doing a simple linear scan over the input and finding the two values. This then gives us an algorithm with the following recurrence:

T(1) <= O(1)
T(n) <= 2T(n / 2) + O(n)

Using the Master Theorem to solve the recurrence, we find that this runs in O(n lg n) time and will use O(lg n) space for the recursive calls. We've just beaten the naive O(n²) solution!

Method 3 - Optimized divide and conquer
But wait! We can do much better than this. Notice that the only reason we have an O(n) term in our recurrence is that we had to scan the entire input trying to find the minimum and maximum values in each half. Since we're already recursively exploring each half, perhaps we can do better by having the recursion also hand back the minimum and maximum values stored in each half! In other words, our recursion hands back three things:

1. The buy and sell times to maximize profit.
2. The minimum value overall in the range.
3. The maximum value overall in the range.

These last two values can be computed recursively using a straightforward recursion that we can run at the same time as the recursion to compute (1):

1. The max and min values of a single-element range are just that element.
2. The max and min values of a multiple element range can be found by splitting the input in half, finding the max and min values of each half, then taking their respective max and min.

If we use this approach, our recurrence relation is now

T(1) <= O(1)
T(n) <= 2T(n / 2) + O(1)

Using the Master Theorem here gives us a runtime of O(n) with O(lg n) space, which is even better than our original solution!

Method 4 - Use the difference between adjacent element
First find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff[] of size n-1. Now this problems turns into finding the maximum sum subarray of this difference array.

int maxDiff(int arr[], int n)
{
    // Create a diff array of size n-1. The array will hold
    //  the difference of adjacent elements
    int diff[n-1];
    for (int i=0; i < n-1; i++)
        diff[i] = arr[i+1] - arr[i];
 
    // Now find the maximum sum subarray in diff array
    int max_diff = diff[0];
    for (int i=1; i<n-1; i++)
    {
        if (diff[i-1] > 0)
            diff[i] += diff[i-1];
        if (max_diff < diff[i])
            max_diff = diff[i];
    }
    return max_diff;
}

Example
input = 
Time Complexity: O(n)
Auxiliary Space: O(n)

Method 5 - Optimizing the diff approach
We can modify the above method to work in O(1) extra space. Instead of creating an auxiliary array, we can calculate diff and max sum in same loop. Following is the space optimized version.

int maxDiff (int arr[], int n)
{
    // Initialize diff, current sum and max sum
    int diff = arr[1]-arr[0];
    int curr_sum = diff;
    int max_sum = curr_sum;
 
    for(int i=1; i<n-1; i++)
    {
        // Calculate current diff
        diff = arr[i+1]-arr[i];
 
        // Calculate current sum
        if (curr_sum > 0)
           curr_sum += diff;
        else
           curr_sum = diff;
 
        // Update max sum, if needed
        if (curr_sum > max_sum)
           max_sum = curr_sum;
    }
 
    return max_sum;
}

Time Complexity: O(n), Auxiliary Space: O(1)

Method 6 -  Dynamic programming (Preferred and easy :))
But wait a minute - we can do even better than this! Let's think about solving this problem using dynamic programming. The idea will be to think about the problem as follows. Suppose that we knew the answer to the problem after looking at the first k elements. Could we use our knowledge of the (k+1)st element, combined with our initial solution, to solve the problem for the first (k+1) elements? If so, we could get a great algorithm going by solving the problem for the first element, then the first two, then the first three, etc. until we'd computed it for the first n elements.
Let's think about how to do this. If we have just one element, we already know that it has to be the best buy/sell pair. Now suppose we know the best answer for the first k elements and look at the (k+1)st element. Then the only way that this value can create a solution better than what we had for the first k elements is if the difference between the smallest of the first k elements and that new element is bigger than the biggest difference we've computed so far. So suppose that as we're going across the elements, we keep track of two values - the minimum value we've seen so far, and the maximum profit we could make with just the first k elements. Initially, the minimum value we've seen so far is the first element, and the maximum profit is zero. When we see a new element, we first update our optimal profit by computing how much we'd make by buying at the lowest price seen so far and selling at the current price. If this is better than the optimal value we've computed so far, then we update the optimal solution to be this new profit. Next, we update the minimum element seen so far to be the minimum of the current smallest element and the new element.

Since at each step we do only O(1) work and we're visiting each of the n elements exactly once, this takes O(n) time to complete! Moreover, it only uses O(1) auxiliary storage. This is as good as we've gotten so far!
As an example, on your inputs, here's how this algorithm might run. The numbers in-between each of the values of the array correspond to the values held by the algorithm at that point. You wouldn't actually store all of these (it would take O(n) memory!),

Time - O(n), Space - O(1) solution:

public static int findMaxProfit(int[] stockPriceSamples) {
 int maxProfit = 0;
 int minTillNow = stockPriceSamples[0];
 for (int i = 0; i < stockPriceSamples.length; i++) {
  int profit = stockPriceSamples[i] - minTillNow;
  maxProfit = Math.max(profit, maxProfit);
  minTillNow = Math.min(stockPriceSamples[i], minTillNow);
 }
 return maxProfit;
}

Example
input = {5        10         4         6        7}
i = 0, maxProfit = 0, minTillNow=5
i = 1, maxProfit=5, minTillNow=5
i= 2, maxProfit = 5,minTillNow=4
i=3,maxProfit=5,minTillNow=4
i= 4,maxProfit=5,minTillNow=5


References

• http://stackoverflow.com/questions/7086464/maximum-single-sell-profit
• http://www.geeksforgeeks.org/maximum-difference-between-two-elements/
• https://programming4interviews.wordpress.com/2012/02/27/maximize-the-single-sell-profit-of-a-stock/

Read More

Find the largest subarray with sum of 0 in the given array

Problem

An array contains both positive and negative elements, find the largest subarray whose sum equals 0.

Example
int[] input = {4,  6,  3, -9, -5, 1, 3, 0, 2}
int output = {4,  6,  3, -9, -5, 1} of length 6

Solution

Method 1 - Brute force
This is simple. Will write later (incomplete)

Method 2 - Storing the sum upto ith element in temp array
Given an int[] input array, you can create an int[] tmp array where  

tmp[i] = tmp[i - 1] + input[i];

Each element of tmp will store the sum of the input up to that element.

Example

int[] input = {4 |  6| 3| -9| -5| 1| 3| 0| 2}
int[] tmp =   {4 | 10|13|  4| -1| 0| 3| 3| 5}

Now if you check tmp, you'll notice that there might be values that are equal to each other.For example, take the element 4 at index 0 and 3, element 3 at index 6 and 7. So, it means sum between these 2 indices has remained the same, i.e. all the elements between them add upto 0. So, based on that we get {6, 3, -9} and {0}.

Also, we know tmp[-1] = 0. When we have not started the array we have no element added to it. So, if we find a zero inside the tmp array, that means all the numbers starting 0th index to 5th index(where 0 exists in temp) are all 0s, so our subarray becomes {4,6,3, -9,-5,1}.

Out of {6, 3, -9}, {0} and {4,6,3, -9,-5,1}, last one is our answer as it is the largest sub array.

To sum it up
We notice that some values are same in tmp array. Let's say that this values are at indexes j an k with j < k, then the sum of the input till j is equal to the sum till k and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k.

• NOTE: if j + 1 == k, then k is 0 and that's it! ;)
• NOTE: The algorithm should consider a virtual tmp[-1] = 0;
• NOTE: An empty array has sum 0 and it's minimal and this special case should be brought up as well in an interview. Then the interviewer will say that doesn't count but that's another problem! ;)

Here is the code

    public static string[] SubArraySumList(int[] array, int sum)
    {
        int tempsum;
        List<string> list = new List<string>();

        for (int i = 0; i < array.Length; i++)
        {
            tempsum = 0;

            for (int j = i; j < array.Length; j++)
            {
                tempsum += array[j];

                if (tempsum == sum)
                {
                    list.Add(String.Format("[{0}-{1}]", i, j));
                }
            }
        }
        return list.ToArray();
    }

Here is the solution using Hashmap, iterate over it again to get the max subarray:

public static void subArraySumsZero() {
    int [] seed = new int[] {1,2,3,4,-9,6,7,-8,1,9};
    int currSum = 0;
    HashMap<Integer, Integer> sumMap = new HashMap<Integer, Integer>();
    for(int i = 0 ; i < seed.length ; i ++){
        currSum += seed[i];
        if(currSum == 0){
            System.out.println("subset : { 0 - " + i + " }");
        }else if(sumMap.get(currSum) != null){
            System.out.println("subset : { " + (sumMap.get(currSum) + 1) + " - " + i + " }");
            sumMap.put(currSum, i);
        }else
            sumMap.put(currSum, i);
    }
    System.out.println("HASH MAP HAS: " + sumMap);
}

References

• http://stackoverflow.com/questions/5534063/zero-sum-subarray

Read More

Given an array arr[], find the maximum j – i such that arr[j] > arr[i]

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/finding-the-maximum-distance-between-increasing-elements-in-an-array/.

Problem

Given an array arr[], find the maximum j – i such that arr[j] > arr[i].

Example

  Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}
  Output: 6  (j = 7, i = 1)

  Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
  Output: 8 ( j = 8, i = 0)

  Input:  {1, 2, 3, 4, 5, 6}
  Output: 5  (j = 5, i = 0)

  Input:  {6, 5, 4, 3, 2, 1}
  Output: -1 

Solution

Method 1 (Simple but Inefficient)
Run two loops. In the outer loop, pick elements one by one from left. In the inner loop, compare the picked element with the elements starting from right side. Stop the inner loop when you see an element greater than the picked element and keep updating the maximum j-i so far.

code

int maxIndexDiff(int arr[], int n)
{
    int maxDiff = -1;
    int i, j;

    for (i = 0; i < n; ++i)
    {
        for (j = n-1; j > i; --j)
        {
            if(arr[j] > arr[i] && maxDiff < (j - i))
                maxDiff = j - i;
        }
    }

    return maxDiff;
}

Time Complexity: O(n^2)

Method 2 (Efficient)
To solve this problem, we need to get two optimum indexes of arr[]: left index i and right index j. For an element arr[i], we do not need to consider arr[i] for left index if there is an element smaller than arr[i] on left side of arr[i]. Similarly, if there is a greater element on right side of arr[j] then we do not need to consider this j for right index.
So we construct two auxiliary arrays LMin[] and RMax[] such that LMin[i] holds the smallest element on left side of arr[i] including arr[i], and RMax[j] holds the greatest element on right side of arr[j] including arr[j]. After constructing these two auxiliary arrays, we traverse both of these arrays from left to right. While traversing LMin[] and RMa[] if we see that LMin[i] is greater than RMax[j], then we must move ahead in LMin[] (or do i++) because all elements on left of LMin[i] are greater than or equal to LMin[i]. Otherwise we must move ahead in RMax[j] to look for a greater j – i value.

Here is the java code

int maxIndexDiff(int arr[], int n)
{
    int maxDiff;
    int i, j;
 
    int[] LMin = new int[n];
    int[] RMax = new int[n];
 
   // Construct LMin[] such that LMin[i] stores the minimum value
   //    from (arr[0], arr[1], ... arr[i]) 
    LMin[0] = arr[0];
    for (i = 1; i < n; ++i)
        LMin[i] = Math.min(arr[i], LMin[i-1]);
 
    // Construct RMax[] such that RMax[j] stores the maximum value
    //   from (arr[j], arr[j+1], ..arr[n-1]) 
    RMax[n-1] = arr[n-1];
    for (j = n-2; j >= 0; --j)
        RMax[j] = Math.max(arr[j], RMax[j+1]);
 
    // Traverse both arrays from left to right to find optimum j - i
     //   This process is similar to merge() of MergeSort 
    i = 0, j = 0, maxDiff = -1;
    while (j < n && i < n)
    {
        if (LMin[i] < RMax[j])
        {
            maxDiff = max(maxDiff, j-i);
            j = j + 1;
        }
        else
            i = i+1;
    }
 
    return maxDiff;
}

Time Complexity: O(n)
Auxiliary Space: O(n)

Examples of running method 2

Example 1

Input Array         :  [7, 3, 9, 2, 1, 11, 0]
LMin                :  [7, 3, 3, 2, 1, 1 , 0]
IndexOfLeftMinimum  :  [0, 1, 1, 3, 4,  4, 6]

RMax                :  [11,11,11,11,11,11, 0]
IndexOfRightMaximum :  [5, 5, 5, 5, 5,  5, 6]
Distance Array      :  [5, 4, 4, 3, 1,  1, 0]

Maximum value in distance array = 5
Corresponding i (from IndexOfLeftMinimum array)  = 0
Corresponding j (from IndexOfRightMaximum array) = 5
Solution: i=0, j=5

Example 2:

Input Array         :  [0, 1, 2, 3, 4]
IndexOfLeftMinimum  :  [0, 0, 0, 0, 0]
IndexOfRightMaximum :  [4, 4, 4, 4, 4]

Maximum value in distance array = 4
Corresponding i (from IndexOfLeftMinimum array)  = 0
Corresponding j (from IndexOfRightMaximum array) = 4
Solution: i=0, j=4

Example 3:

Input Array         :  [4, 3, 2, 1, 0]
IndexOfLeftMinimum  :  [0, 1, 2, 3, 4]
IndexOfRightMaximum :  [0, 1, 2, 3, 4]

Maximum value in distance array = 0
Corresponding i (from IndexOfLeftMinimum array)  = None
Corresponding j (from IndexOfRightMaximum array) = None
Solution: No such pair

Source -  geeksforgeeks

Read More

Find the appropriate data structure

Lets see if you have solutions to the standard problems. Lets define the suitable data structures.

Guess the data structues between the 2 data structures provided (in italics).

1. Operations are Insert, DeleteMax, and DeleteMin.
   balanced tree or sorted doubly-linked list
   The balanced tree is better since all operations take O(log n) time. The sorted doubly-linked list is O(1) for DeleteMax and DeleteMin, but Insert is O(n); thus, the average time per operation is O(n).
2. Operations are Insert and FindMedian.
   (The median is the item m such that half the items are less than m and half are greater than m.)
   red-black trees or sorted array
   You can use two red-black trees plus an additional variable to hold the median, one red-black tree for items less than the median and one for items greater than the median. When you insert, you can keep track of the median by moving items from one tree to the other. With this scheme, Insert takes O(log n) time and FindMedian take O(1) time. The sorted array takes O(n) time for Insert.
3. You have a dictionary containing the keywords of the Pascal programming language.
   ordered array or red-black tree
   In this situation the ordered array is best. Both data structures take time O(log n) to find an item. An ordered array takes longer to insert or delete, but we don't expect to be creating or destroying keywords, so there shouldn't be any insertion or deletion. The ordered array is simpler to program and takes less space.
4. You have a dictionary that can contain anywhere from 100 to 10,000 words.
   unordered linked-list or red-black tree
   The red/black tree is better, since the operations require O(n) time for the linked-list and O(log n) time for the red/black tree. For 10,000 words this could certainly be significant.
5. You have a large set of integers with operations insert, findMax, and deleteMax.
   unordered array or Hashtable
   Neither data structure is good for this problem. An unordered array is slightly better since it has less overhead and it's easier to program.

Read More

LATIN SQUARE” and its implementation

Problem

Understand Latin Square and its implementation

Understanding the latin square
“A Latin square is an n × n array filled with n different Latin letters, each occurring exactly once in each row and exactly once in each column” – Wikipedia. You can find the detail explanation of the properties of this Square here on Wikipedia

In this article we will build a square to match the definition. As the definition suggest Latin square is square in which the row elements do not repeat and the column elements do no repeat.
This article talks about how to fill numbers.Leonhard Euler however initially proposed it to be filled with Latin characters and thus the name.

So we can ask the question is a Latin square unique for a given dimension.NO, the possibilities are many in fact it is not easily computable.One such calculation by van Lint and Wilson is shown in the Wikipedia article. Our interest is to simply build one such Latin square with numbers.

Latin Square have had various application. One such is they can be used as error correcting codes. Perhaps the most well know application is the game of Sudoku. Sudoku is a special case of Latin square where in the additional property is that for a 9×9 square 3×3 sub squares must contain all the 9 numbers. KenKen puzzles are also a variant of Latin square. They are also used to formulate statistical experiments. Dating services can use Latin squares to Organize meeting between n number of boys and girls (marriage problem). Most popular is scheduling of round-robin tournaments.


IMPLEMENTATION:
Following is a C++ program that displays the for a ‘N’ order dimension, Latin squares of the order N,N-1…1
Firstly the Logic.
Step 1. Generate a array randomly. Lets call this Original
for Eg : Original[ 1 , 2 , 4 , 3 ]
We keep the first digit as it is. From this digit find the index from which we can extract the value and place it accordingly
index = (1 – 1) =0
value[0] = 1
So,
place 1 at (1-1) = 0 index of row 0
place 1 at (2-1) = 1 index of row 1
place 1 at (4-1) = 3 index of row 2
place 1 at (3-1) = 2 index of row 3
partial square looks like ( B – not yet found) – You can see the output to match this derivation
1 B B B
B 1 B B
B B B 1
B B 1 B
Step 2: Now rotate the Original array by one position to the left 2 4 3 1
NOTE : However the index and value are with reference to the original array
Let us derive
First digit – 2 . Index needed = (2-1) = 1
Original[1] = 2 (notice it is not 4 , we are still using values from original array)
So,
place 2 at (2-1) = 1 index of row 0
place 2 at (4-1) = 3 index of row 1
place 2 at (3-1) = 2 index of row 2
place 2 at (1-1) = 0 index of row 3
Now square looks like
1 2 B B
B 1 B 2
B B 2 1
2 B 1 B
You can derive further. So this can be implemented by two function shuffle and rotate. Shuffle will use a random generator function to generate the initial permutation and then use rotate method to do the one shift rotate for n times
Here is a code in cpp-

#include <iostream>
#include <stdlib.h>
#include <iomanip>
 
using namespace std;
 
void shuffle(int array1[], int size)
{
     int i, temp, random, last;
 
     for (i = 0; i < size; i++)
           array1[i] = i + 1;
 
     for (last = size; last > 1; last--)
     {
           random = rand() % last;
           temp = array1[random];
           array1[random] = array1[last - 1];
           array1[last - 1] = temp;
     }
}
 
void rotate(int array2[], int size)
{
     int temp, i;
 
     temp = array2[0];
     for (i = 0; i < size - 1; i++)
           {array2[i] = array2[i+1];}
     array2[size - 1] = temp;
}
 
int main()
{
     int sequence[10],jumbled[10];
     int square[10][10];
     int position, value, i, j, size;
 
     srand((unsigned)time(NULL));
     cout<<"Enter the Dimension of Square you need \n";
     cin>>size;   
      
     while (size != 0)
     {
           shuffle(jumbled, size);
           for (i = 0; i < size; i++){
                 sequence[i] = jumbled[i];}
 
           for (i = 0; i < size; i++)
           {
                 position = sequence[0];
                 value = jumbled[position - 1];
 
                 for (j = 0; j < size; j++){
                       square[j][sequence[j] - 1] = value;}
 
                 rotate(sequence, size);
           }
           cout << endl;
           cout << "A Latin Square of Order " << size << " is: " << endl << endl;
        
           for (i = 0; i < size; i++)
           {
                 for (j = 0; j < size; j++)
         {
                       cout << setw(5) << square[i][j];
                 }
         cout << endl;
           }
         size--;
     }
     return 0;
}

OUTPUT:
Used in explanation
laptop:~/code$ ./a.out
Enter the Dimension of Square you need
4
A Latin Square of Order 4 is:
1 2 4 3
4 1 3 2
3 4 2 1
2 3 1 4
A Latin Square of Order 3 is:
2 1 3
1 3 2
3 2 1
A Latin Square of Order 2 is:
1 2
2 1
A Latin Square of Order 1 is:
1
laptop:~/code$ ./a.out
Enter the Dimension of Square you need
4
A Latin Square of Order 4 is:
1 3 4 2
3 2 1 4
2 4 3 1
4 1 2 3
A Latin Square of Order 3 is:
3 1 2
2 3 1
1 2 3
A Latin Square of Order 2 is:
1 2
2 1
A Latin Square of Order 1 is:
1
A detail explanation about Latin squares is found here at cut the knot site.
Also you can refer to code of a simple Latin square using C here

 Reference
http://chinmaylokesh.wordpress.com/category/data-structures/matrix/
http://www.tylo42.com/latin_square 

Read More

Merge Overlapping Intervals

Problem

Given a collection of intervals, merge all overlapping intervals.

Input - Collection of intervals
Output - Collection of mutually exclusive intervals after merging

Example

Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution

Method 1 - Brute force
A simple approach is to start from the first interval and compare it with all other intervals for overlapping, if it overlaps with any other interval, then remove the other interval from list and merge the other into the first interval. Repeat the same steps for remaining intervals after first. This approach cannot be implemented in better than O(n^2) time.

Method 2 -  Sort on the basis of start time and merge

An efficient approach is to first sort the intervals according to starting time. Once we have the sorted intervals, we can combine all intervals in a linear traversal. The idea is, in sorted array of intervals, if interval[i] doesn’t overlap with interval[i-1], then interval[i+1] cannot overlap with interval[i-1] because starting time of interval[i+1] must be greater than or equal to interval[i].
Following is the detailed step by step algorithm :

1. Sort the intervals based on increasing order of starting time.
2. Select the first element from the collection of intervals. Lets call it A
3. For each interval in the collection do the following
   1. If the current interval does not overlap with the A,do nothing.
   2. If the current interval overlaps with A and ending time of current interval is more than that of stack top, update stack top with the ending time of current interval. Put it in new list called result
4. At the end result collection will contain the merged intervals.

Code in java
In java, we can sort any object provided we write implement the comparator interface. Then we can simply use Collections. sort() utility. You can sort the intervals in other languages, in some other way. So, lets stay language agnostic. I just wanted to update you that.

class Interval {
 int start;
 int end;
 
 Interval() {
  start = 0;
  end = 0;
 }
 
 Interval(int s, int e) {
  start = s;
  end = e;
 }
}

class IntervalComparator implements Comparator<Interval> {
 public int compare(Interval i1, Interval i2) {
  return i1.start - i2.start;
 }
}
 
public class Solution {
 public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
 
  if (intervals == null || intervals.size() <= 1)
   return intervals;
 
  // sort intervals by using self-defined Comparator
  Collections.sort(intervals, new IntervalComparator());
 
  ArrayList<Interval> result = new ArrayList<Interval>();
 
  Interval prev = intervals.get(0);
  for (int i = 1; i < intervals.size(); i++) {
   Interval curr = intervals.get(i);
 
   if (prev.end >= curr.start) {
    // merged case
    Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end));
    prev = merged;
   } else {
    result.add(prev);
    prev = curr;
   }
  }
 
  result.add(prev);
 
  return result;
 }
}

Time complexity - O(n log n) + O(n) = O(n log n)

Read More

Find Local Minimum in an unsorted array with unique elements

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-local-minima-in-a-given-array/.

Problem: Given an array ‘a’ of N distinct integers, design an O(log N) algorithm to find a local minimum: an index i such that a[i-1] > a[i] < a[i+1].

Examples:

a = [1,2,3,4,5] (increasing, increasing) a[0] is an LM
a = [5,4,3,2,1] (decreasing, decreasing) a[n] is an LM
a = [1,2,2,2,1] (increasing, decreasing) a[0] and a[n] are LMs

Solution:

Brute force 
Go through each element 3 tuples, and compare them.
Time complexity - O(n)

Solution 2
Can we do better? The answer is yes, we can do this in O(log n). Lets see how.

mid=(start+end)/2; 
1. If there is just one array element, it's a local minimum.
2. If there are two array elements, check each. One must be a local minimum.
3. Otherwise, look at the middle element of the array. 
   If it's a local minimum, return it. 
   Otherwise, at least one adjacent value must be smaller than this one. 
   Recurse in the half of the array containing that smaller element 
   (but not the middle).

Here is the code in java:

public class LocalMinimum {

 public static int findLocalMinimum(int[] elements, int lowIndex, int highIndex) {
  if (lowIndex > highIndex) {
   return -1;
  }

  if (lowIndex == highIndex) {
   return lowIndex;
  }

  if (lowIndex + 1 == highIndex) {
   if (elements[lowIndex] < elements[highIndex]) {
    return lowIndex;
   }
   return highIndex;
  }

  int midIndex = (lowIndex + highIndex) / 2;

  if ((elements[midIndex] <= elements[midIndex - 1])
    && (elements[midIndex] <= elements[midIndex + 1])) {
   return midIndex;
  }

  if (elements[midIndex] >= elements[midIndex + 1]) {
   return findLocalMinimum(elements, midIndex, highIndex);
  } else {
   return findLocalMinimum(elements, lowIndex, midIndex);
  }
 }
 
 public static void main(String[] args){
  int Arr[] = {8,5,4,3,1,2,6,9};
  int index = findLocalMinimum(Arr, 0, Arr.length-1);
  System.out.println("local mimimum is "+Arr[index]);
 }

}

Time complexity

T(1) ≤ 1
T(2) ≤ 1
T(n) ≤ T(n / 2) + 1

Using the Master Theorem, you can show that this algorithm runs in time O(log n), as required.

[Edit] - Note

1. We are not enumerating all the local minima in the array, but a single LM, which can be done in O(log n) time.
   The number of local minima can be n/2; you can't enumerate them all in O(log n) time.
   
2. It also doesn't guarantee whether we will get global minima or not. Consider the array
   {8,5,4,3,1,2,6,9}, the output will be 1, as it is only LM here, not because it is a global minima.
3. The method doesn't guarantee any particular local minima. Consider the array : {8,5,4,3,6,4,5,1,2,6,4,5,9}. The LM outputted by the code will be 3, which is one of the LMs in the array. The LMs we had in array were 3,4,1,4. But the code returned 3, which is one of the LMs. 

Reference
http://stackoverflow.com/questions/12238241/find-local-minima-in-an-array

Thanks

Read More

How to find max. and min. in array using minimum comparisons?

Problem : Given an array of integers find the max. and min. using minimum comparisons.

Solution
Method 1 (Naive) - Iterate through the array, and update min and max pointers

1. Iterate through the array, select element a
2. Update min by comparing (min, a)
3. Update max by comparing (max, a)

Number of comparison here will be ~2N, if N is number of element.
Time complexity will be O(n) though.

Method 2 - Pick 2 elements at time, compare them and compare them with corresponding min and max

1. Pick 2 elements(a, b), compare them. (say a > b)
2. Update min by comparing (min, b)
3. Update max by comparing (max, a)

This way you would do 3 comparisons for 2 elements, amounting to 3N/2 total comparisons for N elements.(Actually it is 3N/2 if N is even, and 3(N-1)/2 if N is odd)

Example
Consider

A = [a1, a2, a3, a4, a5]

Compare a1 & a2 and calculate min12, max12:

if (a1 > a2)
  min12 = a2
  max12 = a1
else
  min12 = a1
  max12 = a2

Similarly calculate min34, max34. Since a5 is alone, keep it as it is...

This way you would do 3 comparisons for 2 elements, amounting to 3N/2 total comparisons for N elements.


Iterative solution

class Pair 
{
   public int min;
   public int max;
}
public Pair getMinMax(int arr[], int n)
{
  Pair minmax;    
  int i; 
 
  // If array has even number of elements then
  //  initialize the first two elements as minimum and
  //  maximum 
  if (n%2 == 0)
  {        
    if (arr[0] > arr[1])    
    {
      minmax.max = arr[0];
      minmax.min = arr[1];
    } 
    else
    {
      minmax.min = arr[0];
      minmax.max = arr[1];
    }
    i = 2;  // set the startung index for loop 
  } 
 
   // If array has odd number of elements then
   // initialize the first element as minimum and
   // maximum 
  else
  {
    minmax.min = arr[0];
    minmax.max = arr[0];
    i = 1;  // set the startung index for loop 
  }
   
  // In the while loop, pick elements in pair and
  //   compare the pair with max and min so far    
  while (i < n-1) 
  {         
    if (arr[i] > arr[i+1])         
    {
      if(arr[i] > minmax.max)       
        minmax.max = arr[i];
      if(arr[i+1] < minmax.min)         
        minmax.min = arr[i+1];       
    }
    else        
    {
      if (arr[i+1] > minmax.max)       
        minmax.max = arr[i+1];
      if (arr[i] < minmax.min)         
        minmax.min = arr[i];       
    }       
    i += 2; //Increment the index by 2 as two
            //   elements are processed in loop 
  }           
 
  return minmax;
}    

Method 3 - Tournament Method
This is similar to previous method, where we were taking 2 elements at a time. Here we are doing this in local subarray recursively and returning elements accordingly.

Pair MaxMin(array, array_size)
   if array_size = 1
      return element as both max and min
   else if arry_size = 2
      one comparison to determine max and min
      return that pair
   else    // array_size  > 2 
      recur for max and min of left half
      recur for max and min of right half
      one comparison determines true max of the two candidates
      one comparison determines true min of the two candidates
      return the pair of max and min

Here is the code

void minmax (int[] a, int left, int right, int min, int max) {
  int lmin, lmax, rmin, rmax, mid;
  if (left==right) {
    min = a[left];
    max = a[right];
  } else if (right == left+ 1) {
    if (a[left] > a[right]) {
      min = a[right];
      max = a[left];
    } else {
      min = a[left];
      max = a[right];
    }
  } else {
    mid = (left+right) / 2;
    minmax(a,left, mid, lmin, lmax);
    minmax(a, mid + 1,right, rmin, rmax);
    min = (lmin > rmin) ? rmin : lmin;
    max = (lmax > rmax) ? lmax : rmax;
  }
}

Thanks.

References -stackoverflow , geeksforgeeks

Read More

Find increasing 3-tuple (sub-sequence)

Problem:
You given an array:
3, 2, 1, 6, 5, 4, 9, 8, 7
you have to find a 3 tuple which has property a < b < c, also a is before b, b is before c in array.
Answer can have multiple tuples, you have to find any one.
In this array, answer will be 3, 6, 9

Solution:

1. Simple. Time complexity = O(n ^ 2)
• Create an array of indexes, and sort the original array keeping track of the indexes in the second array. Now go through the sorted array and for each element try to find a pair of grater elements whose indexes are increasing. Complexity: time = O(n log n) + O(n ^ 2) = O(n ^ 2), space = O(n)
• Alternatively, traverse the original array starting from the second element and consider it to be the middle of the 3-tuple. Try to find a smaller element at indexes [0..i) and a greater element at (i..n]. Complexity: time = O(n ^ 2), space = O(1)
• Or, build a BST from the original array. Then find an element having two consecutive right children. They are grater than one another due to the BST property, and they are located one after another in the original array because we added them in this order in the BST. Complexity: time = O(n ^ 2) [worst] + O(n) = O(n ^ 2), space = O(n)
2. Advanced.
   Search for Longest Increasing Subsequence and stop after finding three elements of the tuple. Time complexity = O(n log n), space = O(n)

From Wikipedia:

Denote the sequence values as X[1], X[2], etc. Then, after processing X[i], the algorithm will have stored values in two arrays:

M[j] — stores the position k of the smallest value X[k] such that there is an increasing subsequence of length j ending at X[k] on the range k ≤ i (note we have j ≤ k ≤ i here, because j represents the length of the increasing subsequence, and k represents the position of its termination. Obviously, we can never have an increasing subsequence of length 13 ending at position 11. k ≤ i by definition).

P[k] — stores the position of the predecessor of X[k] in the longest increasing subsequence ending at X[k].

In addition the algorithm stores a variable L representing the length of the longest increasing subsequence found so far. Note that, at any point in the algorithm, the sequence

X[M[1]], X[M[2]], ..., X[M[L]]

is nondecreasing. For, if there is an increasing subsequence of length i ending at X[M[i]], then there is also a subsequence of length i-1 ending at a smaller value: namely the one ending at X[P[M[i]]]. Thus, we may do binary searches in this sequence in logarithmic time. The algorithm, then, proceeds as follows.

L = 0
for i = 1, 2, ... n:
   binary search for the largest positive j ≤ L
     such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
   P[i] = M[j]
   if j == L or X[i] < X[M[j+1]]:
      M[j+1] = i
      L = max(L, j+1)

The result of this is the length of the longest sequence in L. The actual longest sequence can be found by backtracking through the P array: the last item of the longest sequence is in X[M[L]], the second-to-last item is in X[P[M[L]]], etc. Thus, the sequence has the form

..., X[P[P[M[L]]]], X[P[M[L]]], X[M[L]].

Complexity:

time - O(n log n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=21602662
http://en.wikipedia.org/wiki/Longest_increasing_subsequence

Read More

Merge two arrays efficiently - one sorted, another unsorted

Problem

Given a sorted array of n elements followed by an unsorted array of length n. Sort the 2 list into one efficiently.

Solution

Method 1 - Insert the elements in sorted array using binary search
Since inserting a single element into array and keeping it sorted is O(n), you cannot get better then that.
Thus, for both cases - sorting the smaller array and then using merge(part1,part2) will be O(n), and thus optimal in terms of asymptotic complexity.

• sorting the smaller array: O(logn*loglog(n)), or O(sqrt(n)*log(sqrt(n)) respectively of the cases.
• merge(part1,part2): O(n+logn) or O(n+sqrt(n)), which is O(n)¹ anyway.

So, the total complexity of both cases is O(n), which is optimal for this problem.




Source

• http://stackoverflow.com/questions/13862701/merge-two-arrays-efficiently-one-sorted-another-unsorted

Read More

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].
e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]

http://stackoverflow.com/questions/6153915/merging-of-two-sorted-halfs-without-extra-memory

Read More

k-way merge - Merging k sorted arrays of n elements

 Given k sorted arrays of size n each, merge them and print the sorted output.
Example:

Input:
k = 3, n =  4
arr[][] = { {1, 3, 5, 7},
            {2, 4, 6, 8},
            {0, 9, 10, 11}} ;

Output: 0 1 2 3 4 5 6 7 8 9 10 11 

Method 1 - Merging from 1 array to other
It does so by using the "merge" routine central to the merge sort algorithm to merge array 1 to array 2, and then array 3 to this merged array, and so on until all k arrays have merged.

Time complexity - O(n . k^2)

It doesn't traverse each of the k arrays once. The first array is traversed k-1 times, the first as merge(array-1,array-2), the second as merge(merge(array-1, array-2), array-3) ... and so on.
The result is k-1 merges with an average size of n*(k+1)/2 giving a complexity of O(n*(k^2-1)/2) which is O(nk^2).
The mistake you made was forgetting that the merges are done serially rather than in parallel, so the arrays are not all size n.

Method 2 - Merge 2 at a time, again and again.
Step 1: Merge arrays (1 and 2), arrays (3 and 4), and so on. (k/2 array merges of 2n, total work kn).
Step 2: Merge array (1,2 and 3,4), arrays (5,6 and 7,8), and so on (k/4 merges of 4n, total work kn).
Step 3: Repeat...
There will be log(k) such "Steps", each with kn work. Hence total work done = O(k.n.log(k)).
Even otherwise, if we were to just sort all the elements of the array we could still merge everything in O(k.n.log(k.n)) time.

 Method 3 - Maintain k min heaps, and get the min element from all the arrays and saving into one
A simple solution is to create an output array of size n*k and one by one copy all arrays to it. Finally, sort the output array using any O(nLogn) sorting algorithm. This approach takes O(nkLognk) time.
We can merge arrays in O(nk*Logk) time using Mean Heap. Following is detailed algorithm.
1. Create an output array of size n*k.
2. Create a min heap of size k and insert 1st element in all the arrays into a the heap
3. Repeat following steps n*k times.
     a) Get minimum element from heap (minimum is always at root) and store it in output array.
     b) Replace heap root with next element from the array from which the element is extracted. If the array doesn’t have any more elements, then replace root with infinite. After replacing the root, heapify the tree.

Source
http://stackoverflow.com/questions/11026219/why-is-k-way-merge-onk2
http://www.geeksforgeeks.org/merge-k-sorted-arrays/

Read More

Find the maximum repeating number in array where all the elements are in range 0 to k-1, k ∈ [0,N]

:

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-element-which-appears-maximum-number-of-times-in-the-ranged-array/.

Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k <= n. Find the maximum repeating number in this array. For example, let k be 10 the given array be arr[] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, the maximum repeating number would be 2. Expected time complexity is O(n) and extra space allowed is O(1). Modifications to array are allowed.

Solution 1 - Brute force
The naive approach is to run two loops, the outer loop picks an element one by one, the inner loop counts number of occurrences of the picked element. Finally return the element with maximum count. Time complexity of this approach is O(n^2).

Solution2 - Using element as index in auxiliary array for counting the frequency
A better approach is to create a count array of size k and initialize all elements of count[] as 0. Iterate through all elements of input array, and for every element arr[i], increment count[arr[i]]. Finally, iterate through count[] and return the index with maximum value. This approach takes O(n) time, but requires O(k) space.

Solution 3 - Using modulo operator
Following is the O(n) time and O(1) extra space approach. Let us understand the approach with a simple example where arr[] = {2, 3, 3, 5, 3, 4, 1, 7}, k = 8, n = 8 (number of elements in arr[]).
1) Iterate though input array arr[], for every element arr[i], increment arr[arr[i]%k] by k (arr[] becomes {2, 11, 11, 29, 11, 12, 1, 15 })
2) Find the maximum value in the modified array (maximum value is 29). Index of the maximum value is the maximum repeating element (index of 29 is 3).
3) If we want to get the original array back, we can iterate through the array one more time and do arr[i] = arr[i] % k where i varies from 0 to n-1.
How does the above algorithm work? Since we use arr[i]%k as index and add value k at the index arr[i]%k, the index which is equal to maximum repeating element will have the maximum value in the end. Note that k is added maximum number of times at the index equal to maximum repeating element and all array elements are smaller than k.
Following is C++ implementation of the above algorithm.

#include<iostream>
using namespace std;
 
// Returns maximum repeating element in arr[0..n-1].
// The array elements are in range from 0 to k-1
int maxRepeating(int* arr, int n, int k)
{
    // Iterate though input array, for every element
    // arr[i], increment arr[arr[i]%k] by k
    for (int i = 0; i< n; i++)
        arr[arr[i]%k] += k;
 
    // Find index of the maximum repeating element
    int max = arr[0], result = 0;
    for (int i = 1; i < n; i++)
    {
        if (arr[i] > max)
        {
            max = arr[i];
            result = i;
        }
    }
 
    /* Uncomment this code to get the original array back
       for (int i = 0; i< n; i++)
          arr[i] = arr[i]%k; */
 
    // Return index of the maximum element
    return result;
}
 
// Driver program to test above function
int main()
{
    int arr[] = {2, 3, 3, 5, 3, 4, 1, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 8;
 
    cout << "The maximum repeating number is " <<
         maxRepeating(arr, n, k) << endl;
 
    return 0;
}

Output : The max repeating number is 3

What else?
The above solution prints only one repeating element and doesn’t work if we want to print all maximum repeating elements. For example, if the input array is {2, 3, 2, 3}, the above solution will print only 3. What if we need to print both of 2 and 3 as both of them occur maximum number of times. Write a O(n) time and O(1) extra space function that prints all maximum repeating elements. (Hint: We can use maximum quotient arr[i]/n instead of maximum value in step 2).
Note that the above solutions may cause overflow if adding k repeatedly makes the value more than INT_MAX.
This article is compiled by Ashish Anand and reviewed by GeeksforGeeks team. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Read More

Finding the max repeated element in an array

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-most-frequent-element-in-the-array/.

Problem : Find the element which occurs maximum number of times.

METHOD 1 : Sorting the array and scanning the array
The simple solution is to
1) Sort the array
2) Scan the array such that keep the track of the elements which occurred max number of times

METHOD 2 : Using Binary Search Tree

We can have a binary search tree with an extra field count, which indicates the number of times an element appeared in the input. 
Node of the Binary Search Tree (used in this approach) will be as follows.

struct tree
{
  int element;
  int count;
}BST;

1) Insert elements in BST one by one and if an element is already present then increment the count of the node.
2) Now do the inorder traversal on the tree, keeping track of the count and value of max element in the tree.

Time complexity - O(n) + O(n) ≈ O(n). First for contructing the tree and second for inorder traversal.

Space complexity - O(2n)  ≈ O(n), since every node needs 2 extra pointers.

METHOD 3 : Using Hashtable
Use a counter for each elements, as value and key as the element in the hashtable. At the end just retun the element having max counter.

Time complexity - O(n) and space complexity O(n) needed for storing in hashtable.

Read More

3 sum problem

Problem Statement:

Problem

Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = 0.

 Making more generic:

 Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = T.

Solution

Brute force approach is of O(n^3) but we can solve it in O(n^2) by using the approach in 2 sum problem approach.

Method 1 - Brute Force

A simple method is to generate all possible triplets and compare the sum of every triplet to 0. 

Code (Java)

boolean threeSumBrute(int arr[], int sum=0)
{  
  int n = arr.length;
    // Fix the first element as A[i]
    for (int i = 0; i < n-2; i++)
    {
       // Fix the second element as A[j]
       for (int j = i+1; j < n-1; j++)
       {
           // Now look for the third number
           for (int k = j+1; k < n; k++)
           {
               if (arr[i] + arr[j] + arr[k] == sum)
               {
                 System.out.printf("Triplet is %d, %d, %d", arr[i], arr[j], arr[k]);
                 return true;
               }
           }
       }
    }
 
    // If we reach here, then no triplet was found
    return false;
}
// calling
int arr[] = {1, -4, 45, -6, 10, 8};
boolean ifExist = threeSumBrute(arr)
//Output = -4, -6, 10
 

Time complexity - O(n^3) 

Method 2 - Using Sorting

First sort the array(Order O(nlogn)), than finding a, b, c pairs is equal to finding=> For every element a in the array, if there exists a pair with sum equal to -a. As explained in 2 sum problem, we can get the pair with sum -a in O(n) and we have to repeat this exercise n times so order of complexity will be O(n^2).

Code (Java)

boolean threeSumSorting(int A[], int sum)
{
    int l, r;
    int n = A.length;
    Arrays.sort(A);
 
    // Now fix the first element one by one and find the
    //   other two elements 
    for (int i = 0; i < n - 2; i++)
    {
 
        // To find the other two elements, start two index variables
        // from two corners of the array and move them toward each
        // other
        l = i + 1; // index of the first element in the remaining elements
        r = n-1; // index of the last element
        while (l < r)
        {
            if( A[i] + A[l] + A[r] == sum)
            {
                System.out.printf("Triplet is %d, %d, %d", A[i], A[l], A[r]);
                return true;
            }
            else if (A[i] + A[l] + A[r] < sum)
                l++;
            else // A[i] + A[l] + A[r] > sum
                r--;
        }
    }
 
    // If we reach here, then no triplet was found
    return false;
}

Time complexity : O(n^2)

Here is the gist for this problem : https://gist.github.com/kinshuk4/eed182627f6c7cf5a7e94282801569a6
Reference

• http://en.wikipedia.org/wiki/3SUM 
• http://leetcode.com/2010/04/finding-all-unique-triplets-that-sums.html 
• http://tianrunhe.wordpress.com/2012/07/07/finding-all-unique-triplets-that-sums-to-zero-3sum/

Read More

Introduction of Array

This is the basic or simplest type of data structure. An array can be defined as, a list of a finite number "n" of similar data elements referenced respectively by a set of n consecutive numbers, usually 1, 2, 3, ..., n.

If A is chosen for the name of some array, then the elements of A are denoted as,
a1, a2, a3, a4, ..., an
OR  A(1), A(2), A(3), A(4), ..., A(n)
OR  A[1], A[2], A[3], A[4], ..., A[n]

Regardless of the notation, the number K in A[K] is called a subscript and A[K] is called a subscripted variables.

There are some important points related to array:

• Data type may be either fundamental data type or user defined data type.
• Array may be any valid variable name.
• Size of array is numeric value which defines the size of the array.

Array can be 1- dimensional and multidimensional. Usually 2 - dimensional array is called as matrix.

2 - D Array can be implemented in memory in 2 ways:

1. Row major order implementation
2. Column major order implementation

Read More

find four elements in array whose sum equal to a given number X

This can be solved efficiently via using HashTables.

We can have a hashtable sums sums will store all possible sums of two different elements. For each sum S it returns pair of indexes i and j such that a[i] + a[j] == S and i != j. But initially it's empty, we'll populate it on the way. So, this can be done in O(n^2) time.

Pseudocode

for (int i = 0; i < n; ++i) {
    // 'sums' hastable holds all possible sums a[k] + a[l]
    // where k and l are both less than i

    for (int j = i + 1; j < n; ++j) {
        int current = a[i] + a[j];
        int rest = X - current;
        // Now we need to find if there're different numbers k and l
        // such that a[k] + a[l] == rest and k < i and l < i
        // but we have 'sums' hashtable prepared for that
        if (sums[rest] != null) {
            // found it
        }
    }

    // now let's put in 'sums' hashtable all possible sums
    // a[i] + a[k] where k < i
    for (int k = 0; k < i; ++k) {
        sums[a[i] + a[k]] = pair(i, k);
    }
}

Thanks.

Read More

Array Implementation of Heap

We have discussed a heap as binary tree. Normal implementation of tree is via pointer, but in heap it is much more efficient to use arrays.

So, suppose we have following heap (having 9 elements) :

Now, we need array of 9 elements.

Now, we see the heap having 3 levels, level 0 as root, and level 3 which is partially filled.

Now, we start putting the elements one by one.
So, level 0 goes at first position, level 2 goes next and so on.

You, might be wondering why we are not wasting any space, and we dont even require pointers. This is coming from properties of almost complete binary tree. For finding parent of the node, we just need

parent(i)
{
   if(i is even)
     return i;
   else
     return floor(i/2);
}

Similarly children of i are:

leftChild(i)
{
   return 2*i;
}

rightChild(i)
{
   return 2*i+1;
}

Read More

Find Nth largest element in the rotated sorted array

Question : Find Nth largest element in the rotated sorted array
So for example we have sorted array as  -

2,3,6,12, 15, 18.

Now suppose the array is rotated k times ( we don't know k), such that array becomes

15, 18,2,3,6,12

Solution
So, to find the Nth largest element in normal sorted array is a[N]. But in this case it is rotated k, which we don't know. But seeing the above array we cans see that k = 2, which is also the index of minimum element i.e. 2 here. So, 3rd largest element is counting 3rd from 2 i.e. 6. Similarly for Nth largest element, it is k+N-1. But as we can see as the array is rotated, k+N-1 may overflow array, so we need to modulo operator on k+N-1, i.e. Nth largest element lies at = (k+N-1)%arraySize.

So, the problem breaks down in 2 step

1. Find k, i.e. number of rotations. To do so please refer the post - Find the rotation count in rotated sorted array
2. Return the arr[(k+N-1)%arr.size]

Here is the pseudocode:

int findNthHigehest(int[] arr, int size, int n)
{
    int k = findRotationCount(arr, size);
    return arr[(n+k-1)%size];
}

Thanks.

Read More

Find the rotation count in rotated sorted array

Question : Find the minimum element in the rotated sorted array.
So for example we have sorted array as  -

2,3,6,12, 15, 18.

Now suppose the array is rotated k times ( we don't know k), such that array becomes

15, 18,2,3,6,12

Solution
This can be solved in linear time and logarithmic time. If we notice the above array, we see the array has been rotated 2 times, which is also the index of smallest element in the array.
So, we need to find the point of inflection where we find a point such that a[i]>a[i+1].

So, finding the minimum element in the rotated sorted array has been implemented here - Find the minimum element in rotated sorted array. Thanks.

Read More