Yahoo Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
The solution you pointed out is not O(n). Though it's better than O(n^2) on average, but its worst case is still O(n^2).
A different solution can use tree, when add a right leaf, update j, and keep the max j - i that A[j] > A[i].
Complexity is less than O(n^)
sites.google.com/site/spaceofjameschen/home/tree/find-the-maximum-j---i-such-that-a-j-a-i
The solution presented in the page is O(n) as it traverse the list in the worst case 4 times.
Nice solution James using tree with average case O(nlogn). Worst case of constructing binary search tree is still O(n^2) though.
That was a great article. Here's a java version of the "efficient" version of that code:
public class IndicesMaxDiff {
/*
Yahoo!:
Given an Array A[], find the maximum j - i such that A[j] > A[i].
For example Input { 34,8,10,3,2,80,30,33,1} and Output 6 (j=7, i=1)
Time Complexity should be less then O(n^2)
*/
/* For a given array arr[], returns the maximum j – i such that
arr[j] > arr[i] */
public static int maxIndexDiff(int[] arr)
{
int maxDiff;
int i, j;
int n = arr.length;
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 = Math.max(maxDiff, j-i);
j = j + 1;
}
else
i = i+1;
}
return maxDiff;
}
/* Driver program to test above functions */
public static void main(String[] args) {
int[] arr = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};
int maxDiff = maxIndexDiff(arr);
System.out.println("Max diff for " + Arrays.toString(arr) + " is " + maxDiff + ".");
return;
}
To whoever said that solution is O(n^2), I'd love to hear more of an explanation. I'm with nperez who points out that it's 4 passes that are at most n long which is still O(n)
The tree solution will be O(n^2) in the worst case because of the tree creation step, not while traversing it. For example, if all values are already in sorted and increasing order, your tree will break down into a linked list, as you are always inserting a right child. This will cause O(n) insertion for each of the N elements, or O(n^2).
This one requires more logic chops than programming chops. If an array has a max gap of 1, we can save ourselves from iterating through every 1-gap solution by instead ruling out all non-1 solutions. I believe this is the only way to achieve a time complexity less than O(n^).
#!/usr/bin/ruby
# Given an Array A[], find the maximum j - i such that A[j] > A[i].
# For example Input {34,8,10,3,2,80,30,33,1} and Output 6 (j=7(33), i=1(34))
# Time Complexity should be less then O(n^2)
class Array
def maxgap
# If all elements are equal, return zero
if self.count(self[0]) == self.size
return 0
end
# If elements are sorted in descending order, return -1
# which is the lowest return possible
for i in 1...self.size do
if self[i - 1] >= self[i] && i == self.size - 1
return -1
elsif self[i - 1] >= self[i] && i != self.size - 1
next
else
break
end
end
# Look for all possible results between max and 2
(self.size - 1).downto(2) do |maxlength|
for i in 0..self.size - maxlength - 1 do
if self[i + maxlength] > self[i]
return maxlength
end
end
end
# At this stage, all possible results besides 1 are
# ruled out so 1 must be the correct answer.
return 1
end
end
puts [34,8,10,3,2,80,30,33,1].maxgap
# => 6
You can apply the following logic as of binary search although the complexity is linear:
a. Find the middle element of the array
b. In order to find the max difference the indices should be as far as possible. So if arr[mid]>arr[low] find the index difference and if this difference is greater than the difference calculated so far then update this diff.
c. Similarly if arr[high]>arr[mid] find the difference as mentioned above.
d. Also find the difference of arr[high]-arr[low]. Suppose the starting and ending index of the sub-array are such that arr[high]>arr[low] then this would be the max difference
e. Also further check it for low+1,high and also for low,high-1
Below is the code:
#include <stdio.h>
#include <conio.h>
static int diff;
void findMaxDiff(int arr[],int low,int high)
{
if(low==high)
return;
if(low+1==high)
{
if(arr[high]>arr[low])
{
int d=high-low;
if(d>diff)
diff=d;
}
return;
}
else
{
int mid=low+(high-low)/2;
if(arr[mid]>arr[low])
{
int d=mid-low;
if(d>diff)
diff=d;
}
if(arr[high]>arr[mid])
{
int d=high-mid;
if(d>diff)
diff=d;
}
if(arr[high]>arr[low])
{
int d=high-low;
if(d>diff)
diff=d;
}
findMaxDiff(arr,low,high-1);
findMaxDiff(arr,low+1,high);
}
}
int main()
{
int arr[]={65,23,12,43,33,13,67,78,54,21};
int n=sizeof(arr)/sizeof(arr[0]);
findMaxDiff(arr,0,n-1);
printf(" The max j-i diff is %d ",diff);
}
public static int run(int[] A){
int dinstanceMax = 0;
//The max cases :
// {j-i = length-1} > { j-i = length -2} > {j-i = length -3} >... > { j-i = -(length-1)}
// check A[j] > A[i] where any j - i > distanceMax
for(int j=A.length-1; j>=dinstanceMax; j--){
for(int i = 0; j - i>dinstanceMax ; i++){
//System.out.println("A["+j+"] : " + A[j]+" A["+i+"] : " + A[i]);
if(A[j] > A[i]){
System.out.println("A["+j+"] : " + A[j]+" A["+i+"] : " + A[i]);
dinstanceMax = j-i;
}
}
}
return dinstanceMax;
}
public static int run(int[] A){
int dinstanceMax = 0;
//The max cases :
// {j-i = length-1} > { j-i = length -2} > {j-i = length -3} >... > { j-i = -(length-1)}
// check A[j] > A[i] where any j - i > distanceMax
for(int j=A.length-1; j>=dinstanceMax; j--){
for(int i = 0; j - i>dinstanceMax ; i++){
//System.out.println("A["+j+"] : " + A[j]+" A["+i+"] : " + A[i]);
if(A[j] > A[i]){
System.out.println("A["+j+"] : " + A[j]+" A["+i+"] : " + A[i]);
dinstanceMax = j-i;
}
}
}
return dinstanceMax;
}
Sorry for java code. The code doesn't uses the auxilary memory, no recursion and still does it in O(n). Please let me know if you find any fault in the code.
import java.util.Arrays;
public class MaxIGreaterJ {
public static int maxDiff(int arr[]){
int maxDiff = -1;
boolean breakCondition = false;
for(int i= 0 ; i< arr.length; i++){
int j=arr.length-1;
if(maxDiff > (j-i)) {
break;
}
while(i<j){
if( arr[i] < arr[j] && maxDiff < (j-i) && breakCondition ){
System.out.println("i= " + i +" j= " + j);
return (j-i);
}else if(arr[i] < arr[j] && maxDiff < (j-i)){
breakCondition = true;
maxDiff = j-i;
break;
}
j--;
}
}
return maxDiff;
}
public static boolean isAllAreDescending(int arr[]){
boolean swap =true;
int i=0;
while(i<1){
i++;
swap = false;
for(int j =0; j < arr.length-i;j++){
if(arr[j] < arr[j+1]){
swap =true;
break;
}
}
}
return !swap;
}
public static void maxDiffCaller(int arr[]){
if(isAllAreDescending(arr)){
System.out.println(" " + -1);
}else {
System.out.println(" " + maxDiff(arr));
}
}
public static void main(String args[]){
int arr1[] = new int[] {34, 8, 10, 3, 2, 80, 30, 33, 1};
maxDiffCaller(arr1);
int arr2[] = new int[] {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};
maxDiffCaller(arr2);
int arr3[] = new int[] {6, 5, 4, 3, 2, 1};
maxDiffCaller(arr3);
}
}
Sorry for java code. The code doesn't uses the auxilary memory, no recursion and still does it in O(n). Please let me know if you find any fault in the code.
import java.util.Arrays;
public class MaxIGreaterJ {
public static int maxDiff(int arr[]){
int maxDiff = -1;
boolean breakCondition = false;
for(int i= 0 ; i< arr.length; i++){
int j=arr.length-1;
if(maxDiff > (j-i)) {
break;
}
while(i<j){
if( arr[i] < arr[j] && maxDiff < (j-i) && breakCondition ){
System.out.println("i= " + i +" j= " + j);
return (j-i);
}else if(arr[i] < arr[j] && maxDiff < (j-i)){
breakCondition = true;
maxDiff = j-i;
break;
}
j--;
}
}
return maxDiff;
}
public static boolean isAllAreDescending(int arr[]){
boolean swap =true;
int i=0;
while(i<1){
i++;
swap = false;
for(int j =0; j < arr.length-i;j++){
if(arr[j] < arr[j+1]){
swap =true;
break;
}
}
}
return !swap;
}
public static void maxDiffCaller(int arr[]){
if(isAllAreDescending(arr)){
System.out.println(" " + -1);
}else {
System.out.println(" " + maxDiff(arr));
}
}
public static void main(String args[]){
int arr1[] = new int[] {34, 8, 10, 3, 2, 80, 30, 33, 1};
maxDiffCaller(arr1);
int arr2[] = new int[] {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};
maxDiffCaller(arr2);
int arr3[] = new int[] {6, 5, 4, 3, 2, 1};
maxDiffCaller(arr3);
}
}
#include <iostream>
#define N 9
using namespace std;
int main()
{
int A[N] = {34,8,10,3,2,80,30,33,1};
int offset = 0;
for(unsigned short int z=1; z<N-1; ++z)
{
unsigned short int y=0;
while(y<z)
{
if(A[z]>A[y] && y<z)
{
offset = z - y;
break;
}
++y;
}
}
cout << "Offset : " << offset << endl;
return 0;
}
How about this: we first sort the array according to the values A[i] into B, while keeping the index information so that if A[i] is the j-th smallest element in A, then B[j] = i. Then the question becomes: find two elements B[k] and B[l] in B so that: (1) k < l (2) B[l]-B[k] is maximized. This is just the one-time-max-profit-stock problem (see Introduction to Algorithms), which can be recast into a "maximum subarray" problem.
Please correct me if I am wrong.
public static void findMdiff(int a[])
{
if(a.length==0)
{ System.out.println("Null array"); System.exit(0);}
if(a.length==1)
{ System.out.println("The max Diff is 0"); System.exit(0);}
int min=0;int max=0;
for(int i=1;i<a.length;i++)
{
if(a[i]<a[min])
{
min=i;
}
else if(a[i]>a[max])
{
max=i;
}
else
continue;
}
System.out.println("The difference is great at "+max+" and "+min+" and the diff is : "+ (a[max]-a[min]));
}
function maximumApart(arr) {
var i;
var j;
var result = [0, 0];
for (i = 0; i < arr.length; i++) {
if (arr.length - 1 - i < result[0] - result[1]) {
break;
}
for (j = arr.length - 1; j > i; j--) {
if (arr[j] > arr[i]) {
if (j - i > result[0] - result[1]) {
result[0] = j;
result[1] = i;
}
break;
}
}
}
console.log(result);
return result[0] - result[1];
}
var assert = require('assert');
assert.equal(maximumApart([34,8,10,3,2,80,30,33,1]), 6);
#include<iostream>
using namespace std;
int main()
{
// int a[] = {20,2,3,17,18};
// int a[] = {145,146,47,10,9,8,7,6,100};
// int a[] = {34, 8, 10, 3, 2, 80, 30, 33, 1};
int a[] = {4,3,5,2,1,3,2,3};
int i = 0, j = ( sizeof(a) / sizeof(a[0]) -1 );
int max_diff = -1 ;
int temp = j;
int pos_max = -1;
while( i <= j || pos_max == -1 )
{
if( a[j] > a[i] )
{
if ( max_diff < j - i)
{
max_diff = j - i;
pos_max = j;
}
i++;
j = temp;
}
else if (i == j)
{
i++;
j=temp;
}
else
{
j--;
}
}
cout<<"MAXIMUM DIFF : "<<max_diff;
}
Start one iterator at the start, keep track of min/ min position of this iterator.
Start one iterator at the end, keep track of max/ max position of this iterator.
Iterate from begin to end and end to begin with two iterators. When you notice max - min is greater than 1. Return the max position and min position. Fail if iterators cross middle O(N) speed O(1) space
Logic to search jthIndex and ithIndex for a[jthIndex]>a[ithIndex]
Note: ithIndex can be greater then jthIndex for some case and (j-i) could be best possible lesser -ve value
Ex: 9 8 7 6 5 4 3 1
Logic: Search for all possible couple for indexDiff where indexDiff is looping from (arraylength-1) to 1. Whenever I got a[jthIndex] > [index] for very first time... those ithIndex and jthIndex will be our ans.
Code:
void getMaxIndexDiffForCondition(int a[])
{
int ithIndex;
int jthIndex;
int flag;
int indexdiff;
flag = 0;
indexDiff = 0;
for(indexDiff = (a.length-1); indexDiff > 0; indexDiff++)
{
ithIndex = 0;
jthIndex = indexDiff;
while (jthIndex < a.length)
{
if(a[jthIndex] > a[ithIndex])
{
flag = 1;
break;
}
else
{
ithIndex++;
jthIndex++;
}
}
if(flag==1)
{
break;
}
}
cout<<"best possible i and j for max (j-i) in such a way that a[j]>a[i] are:";
cout<<"index j="<<j;
cout<<"index i="<<i;
cout<<"element diff is"<<a[j]-a[i];
cout<<"index diff is"<<(j-1);
}
My answer suggestion: Please give comments
This idea will take extra space for index and original array. But time complexity will be less than square of n.
step 1: store the indices of the array and elements into 'index' and 'array'.
step 2: sort the elements using quick sort and store the indices of the element into the index array during the swap method. We will have the index with elements sorted.
step 3: use the following Find method to get the maximum element.
Idea of the Find method.
Start from end of the original array. Start from beginning of the sorted array. If the element of the sorted array is less than original array, get the max separation by subtracting indices of the sorted array from present indices of the original array.(please see the find method)
Exit both for loops if the max separation is greater than the iterator of the first for loop.
namespace LargestSeperationBetweenAiLessAj
{
class Program
{
public static float[] main = { 34, 8, 10, 3, 2, 80, 30, 33, 1 };
public static int[] index;
public static float[] orginal;
static void Main(string[] args)
{
index=new int[main.Length];
orginal = new float[main.Length];
//sort the numbers.
//store the index of the sorted numbers
//use quicksort
//go from last till the max <array.lenth-max
for (int i = 0; i < main.Length; ++i)
{
index[i] = i;
orginal[i] = main[i];
Console.Write(index[i] + "=" + main[i] + "\t");
}
Console.WriteLine();
Quicksort();
for (int i = 0; i < main.Length; ++i)
Console.Write(index[i] +"="+main[i] + "\t");
Console.WriteLine("max=" + Find());
Console.Read();
}
public static int Find()
{
int max = 0;
for (int i = orginal.Length - 1; i >= max; --i)
{
for (int j = 0; j <main.Length; ++j)
{
if (main[j] < orginal[i])
{
if (max < (i - index[j]))
{
max = i - index[j];
}
}
else
{
break;
}
}
}
return max;
}
public static void Quicksort()
{
quicksort( 0, index.Length - 1);
}
// quicksort a[left] to a[right]
private static void quicksort( int left, int right)
{
if (right <= left) return;
int i = partition(left, right);
quicksort( left, i - 1);
quicksort( i + 1, right);
}
// partition a[left] to a[right], assumes left < right
private static int partition(
int left, int right)
{
int i = left - 1;
int j = right;
while (true)
{
while (less(main[++i], main[right])) // find item on left to swap
; // a[right] acts as sentinel
while (less(main[right], main[--j])) // find item on right to swap
if (j == left) break; // don't go out-of-bounds
if (i >= j) break; // check if pointers cross
exchange(i, j); // swap two elements into place
}
exchange(i, right); // swap with partition element
return i;
}
// is x < y ?
private static bool less(float x, float y)
{
return (x < y);
}
// exchange a[i] and a[j]
private static void exchange(int i, int j)
{
float swap = main[i];
main[i] = main[j];
main[j] = swap;
int b = index[i];
index[i] = index[j];
index[j] = b;
}
}
}
a nice o(n) sln using o(n) extra space..good explanation too
- Amit July 21, 2013www .geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri/