Amazon Interview Question for Developer Program Engineers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
20
of 22 vote

A Simple and cleaner solution. No need to check for index j > i etc.

private void MaxDiff(int[] a)
       {
           int min = a[0]; // assume first element as minimum
           int maxdiff = 0;
           int posi = -1, posj = -1, minpos = 0;

           for (int i = 1; i < a.Length; i++)
           {
               if (a[i] < min)
               {
                   min = a[i];
                   minpos = i;
               }
               else
               {
                   int diff = a[i] - min;
                   if (diff > maxdiff)
                   {
                       maxdiff = diff;
                       posi = minpos;
                       posj = i;
                   }
               }
           }
           Console.WriteLine("i={0}, j={1}",posi,posj);
       }

- sk February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Well done !

- floaterions December 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how about {7,5,2}, in this example, you never go into the second branch.
when a[i] < min, there is possibility that a[i] - min is maximum.
here is my solution.

#include <vector>
using std::vector;
#include <iostream>
using std::cout;
using std::endl;
#include <cstdio>
#include <cstdlib>

struct pos {
  int j;
  int i;
  int value;
  pos(int a=-1,int b=-1,int c=-1){
    j=a;
    i=b;
    value=c;
  }
};
pos max(const pos &a,const pos &b) {
  return a.value > b.value ? a : b;
}
pos max_sub(const vector<int>& a, int i, int i_min) {
  if(i>a.size()-1 || i<0 || i_min>a.size()-1 || i_min<0 || i<=i_min)
  {
    printf("wrong argument in max_sub(%i,%i).\n",i,i_min);
    exit(-1);
  }
  printf("(%i,%i)\n",i,i_min);
  
  if(i == (a.size() -1))
    return pos(i_min,i,a[i]-a[i_min]);
  if (a[i] < a[i_min]) {
    return max( pos(i_min,i,a[i]-a[i_min]), max_sub(a,i+1,i) );
  } else {
    return max( pos(i_min,i,a[i]-a[i_min]), max_sub(a,i+1,i_min) );
  }
}
int main(int argc, char *argv[])
{
  int c[]=
      {
        3,5,11,20,1
      };
  vector<int> b(c,c+sizeof(c)/sizeof(int));
  for (int i = 0; i < b.size(); ++i) {
    printf("%i ",b[i]);
  }
  cout<<endl;
  pos a = max_sub(b,1,0);
  printf("max_sub = b[%i] - b[%i] = %i\n",a.i,a.j,a.value);
  return 0;
}

- liyichao.good March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

private static void MaxDifference(int[] a) {
		if(a.length == 0){
			System.out.println("Empty Array");
		}
			
		int i = 0, minIndex = 0;
		int j = a.length - 1, maxIndex = a.length - 1;
		int maxDiff = a[j] - a[i];
		int count = 0;
		while(count < a.length - 1){
			if(a[maxIndex] - a[i+1] > maxDiff && a[i+1] < a[minIndex] && maxIndex > i+1){
				minIndex = i+1;
				maxDiff = a[maxIndex] - a[minIndex];
			}
			if(a[j - 1] - a[minIndex] > maxDiff && a[j-1] > a[maxIndex] && minIndex < j-1){
				maxIndex = j-1;
				maxDiff = a[maxIndex] - a[minIndex];
			}
			i++;j--;count++;
			System.out.println("count :" + (count) + " difference : " + maxDiff + "  min value " + a[minIndex] + " max value " + a[maxIndex]);
		}
		System.out.println("difference : " + maxDiff + "  min value " + a[minIndex] + " max value " + a[maxIndex]);
		
	}

- coffee break April 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

sk solution is almost perfect, just doesn't work for { 7, 5, 2 } (answer should be 0, 1) or { 7, 5, 2, 2 } (answer should be 2, 3). Just a minor tweak would made it work correctly. The 2 important factor is maxdiff needs to be Int32.MinValue (not 0), and the if statements needs to be reversed, we need to calculate the dif before moving the min value position.

int min = array[0]; // assume first element as minimum
int maxdiff = Int16.MinValue;
int minpos = 0;
posi = -1;
posj = -1;

for (int i = 1; i < array.Length; i++)
{
int diff = array[i] - min;
if (diff > maxdiff)
{
maxdiff = diff;
posi = minpos;
posj = i;
}
else if (array[i] < min)
{
min = array[i];
minpos = i;
}
}

- Anonymous April 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

The solution is quite simple, one pass:

Start checking from the beginning of the array. Initially there are no min/max values stored.
If the current element is smaller than the stored min, replace the stored min with current element and clear stored max (the stored max is no longer valid for this current min).

If the current item is larger than the current max and larger than the stored min, store it as a max. If this currently stored min/max pair is bigger difference than the previous, overwrite it (this will be the returned value).

To make it visible:

2     1     4     100     -5
Min          2     1     1      1         -5
Max         inv   inv   4      100    inv

When you hit 100, you see the current Min/Max pair is bigger than the previous (1/4) so you store it as the return value. The last one, -5 does not have a valid pair, so you return 1/100.

- Adam February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

will not work for : 3 5 1 2

- tomb February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is the running code enjoy

{public static void printMax(int []a){
		int min,min1,max,x,x1,y;
		min=max=min1=a[0];
		x=x1=y=0;
		for (int i=1;i<a.length;i++){
			if(a[i]>=max){
				max=a[i];
				y=i;
			}
			else if(a[i]<min){
				min1=a[i];
				x1=i;
			}
			if((a[i]-min1)>(max-min)){
				max=a[i];
				min=min1;
				x=x1;
				y=i;
			}
		}
		System.out.println( x);
		System.out.println( y);
		System.out.println( min);
		System.out.println(max);
		}
		
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//int ar[]=new int[10];
		int ar[]={5,15,3,10,20,1,19,0,8,16};
		printMax(ar);
System.out.write(1);
	}

}

- anubhav jain February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It doesn't work when the first element is the largest of the array, for example: 7,5,4,3,1,6

- JL February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes it does:

7     5     4     3     1     6
min     7     5     4     3      1    1
max    inv  inv  inv  inv   inv 6

To tomb:

3    5    1    2
min     3     3    1   1
max    inv  5    inv 2

On the way, 3/5 was stored but 1/2 did not overwrite it

- Adam February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It doesn't work when the first element is the largest of the array, for example: 7,5,4,3,1,6
x 0 y 0min 7max 7

- anyonumus February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include "stdafx.h"
#include <iostream>
#include <cstdlib>
using namespace std;

int main() {
int i,j,i1,j1,max,min,diff,maxdiff;
int a[6] = {1,2,3,4,5,6};
min = 100;
max = -1;
diff = -1;
maxdiff = -1;
for(int k = 0;k < 6;k++) {
if(a[k] < min) {
min = a[k];
max = -1;
i = k;
j = -1;
}
else if(a[k] > max) {
max = a[k];
j = k;
}
if(j!=-1) {
diff = a[j] - a[i];
}
if(diff > maxdiff) {
maxdiff = diff;
i1 = i;
j1 = j;
}
}
cout << maxdiff << i1 << j1;
}

- Dinesh February 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is a draft O(N) algo to find max{j-i,A[j]>A[i]}.
For a given array of numbers A[N] (zero based),
1) Create array B[N]. Init it the following way:
B[0] = A[0];
for(i=1;i<N;++i) B[i] = min(A[i],B[i-1]);
2) Create array C[N]. Init it this way:
C[N-1] = A[N-1];
for(i=N-2;i>=0;--i) C[i] = max(A[i],C[i+1]);
3) Let max_i_j = 0, i=j=0. Now, do this merge type of calculation on B and C:
while(j<N) do {
while(B[i] < C[j] && j<N) j=j+1;
max_i_j = max(max_i_j,j-i);
i=i+1;j=j+1;
}
===============
Each step is O(N). I am sure it can be done some more elegant way though...

- celicom May 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

cool idea!

- anon May 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

explain your logic... i didn't understand how it will work for the input - {20,30,2,11,12,10,1,4}

- swathi May 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

excellent!!

- master fuji May 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Elegant idea

One small fix, should be B[i] <= C[j] in
"while(B[i] < C[j] && j<N) j=j+1;"

- Aaron May 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Aaron
No, Aaron, it should be a strict B[i]<C[j] as we are checking if A[j]>A[i], not A[j]>=A[i]

- celicom May 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is not working for this case

10, 2, 7, 9, 0, 3, 1, 1, 1, 1
the maximum length is from 0 to the last 1, but your algorithm will find the length from 2 to the last 1.

- lyla June 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@lyla,
the minor fix is that j must be less than N when calculating max_i_j,
so the line
while(B[i] < C[j] && j<N) j=j+1;
should be changed to:
while(B[i] < C[j] && j<N-1) j=j+1;

the rest is fine.

For your sequence:
A[10] = {10,2,7,9,0,3,1,1,1,1};
1) B[10] = {10,2,2,2,0,0,0,0,0,0};
2) C[10] = {10,9,9,9,3,3,1,1,1,1};
3) the loop while(j<10) stops with max_i_j = 9-4=5 on i=4,j=9;

- celicom June 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice one !!

- seth July 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

A[8] = {20,30,2,11,12,10,1,4};
1) B[8] = {20,20,2,2 ,2 ,2 ,1,1};
2) C[8] = {30,30,12,12,12,10,4,4};
3) the loop while(j<8) stops with max_i_j = 7-2=5 on i=2,j=7

- celicom May 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It looks good. But I don't understand the philosophy behind this idea.... Could you please explain the meaning of B and C?? Thanks.

- wfchiang May 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@wfchiang
Please check my response to harry below...

- celicom June 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Consider the left point of those pair (i, j) first.
Suppose i < k and A[i] <= A[k]. Then for any k < j and A[k] < A[j], i must be better than k, i.e. k is useless as a "left point"

Now scan from the left of array A, to find all the left point candidates, they must be:
A[i_1] > A[i_2] > A[i_3] > ... > A[i_m], here 1 = i_1 < i_2 < ... < i_m <=n

Keeping a pointer whose initial value is ptr = m,
Second scan from the right side, for every j:

if (i_ptr > j) ptr = ptr - 1;
while (ptr > 1) and (A[i_ptr] >= A[j]) ptr = ptr - 1;
while (ptr > 1) and (A[i_(ptr-1)] < A[j]) ptr = ptr - 1;
checking pair(i_ptr, j)

Finally, we get the maximum (j - i) in O(n) time.

- Frank May 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, it should be:

Consider the left point of those pair (i, j) first.
Suppose i < k and A[i] <= A[k]. Then for any k < j and A[k] < A[j], i must be better than k, i.e. k is useless as a "left point"

Now scan from the left of array A, to find all the left point candidates, they must be:
A[i_1] > A[i_2] > A[i_3] > ... > A[i_m], here 1 = i_1 < i_2 < ... < i_m <=n

Keeping a pointer whose initial value is ptr = m,
Second scan from the right side, for every j:

if (i_ptr > j) ptr = ptr - 1;
if (A[i_ptr] >= A[j]) continue;
while (ptr > 1) and (A[i_(ptr-1)] < A[j]) ptr = ptr - 1;
checking pair(i_ptr, j)

Finally, we get the maximum (j - i) in O(n) time.

- Frank May 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain it in proper way with an example.. the solution seems to be confusing.., and not getting what you are doing?

- putta.sreenivas May 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include <vector>
#include <iostream>
using namespace std;

int solve(vector<int> A) {
vector<int> cand_A;

cand_A.push_back(0); // the left most element of A

// all left candidates
for (int i=1; i<A.size(); ++i) {
if ( A[i] < A[cand_A.back()] )
cand_A.push_back(i);
}

int ptr = cand_A.size() - 1;
int best = -1, bi, bj;

for (int j=A.size()-1; j>=0; --j) {

if (cand_A[ptr] >= j) --ptr;
if (A[ cand_A[ptr] ] >= A[j]) continue;
while ((ptr > 0) && (A[cand_A[ptr-1]] < A[j])) --ptr;

// checking availability
if ((A[ptr] < A[j]) && (j - ptr > best)) {
best = j - ptr;
bi = ptr;
bj = j;
}
}

return best;
}

int main() {
int A[] = {5, 6, 7, 8, 9, 4, 3, 2, 1, 0}; //answer = 4
//int A[] = {4, 2, 1, 5, 8, 1, 3}; //answer = 5
cout << "Answer: " << solve(vector<int> (A, A+sizeof(A)/4)) << endl;
return 0;
}

- Frank May 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, it seems that my safari browser could not add code in the proper way by "Runnable Code" :(

e.g. in case A = {5, 6, 7, 8, 9, 4, 3, 2, 1, 0}
In the first scan,
we get the candidates
{5, 4, 3, 2, 1, 0} with
index[]={0, 5, 6, 7, 8, 9} (zero-base)

Now we scan from the right, start from j = 9, ptr=5.
and achieve our solution when: j = 4, ptr= 0

- Frank May 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Bug fixed:

// checking availability
if ((A[ cand_A[ptr] ] < A[j]) && (j - cand_A[ptr] > best)) {
best = j - ptr;
bi = cand_A[ptr];
bj = j;
}

- Frank May 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am not able to understand ur code properly but it look like a O(n^2)solution to me

- Anonymous May 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
How about this solution?
Suppose we have an array, A[0 ..... n]

if (A[n] > A[0]) then return n;
else return Max(findMax(A[0 ... n-1]), findMax(A[1 ... n]))

So it is a dynamic programming problem.
The worst case is time complexity is O(n^2)
*/

int DPRecord[N][N]; // each cell should be initialized by -1

int findMax(int *A, int i_start, int i_end) {
if (i_end <= i_start) return -1;
if (DPRecord[i_end][i_start] != -1) return DPRecord[i_end][i_start];

if (A[i_end] > A[i_start]) {
DPRecord[i_end][i_start] = A[i_end] - A[i_start];
}
else {
int max1 = findMax(A, i_start+1, i_end);
int max2 = findMax(A, i_start, i_end-1);
DPRecord[i_end][i_start] = max1 > max2 ? max1 : max2;
}

return DPRecord[i_end][i_start];
}

int main (int argc, char *argv[]) {
int answer = findMax(A, 0, length(A));
if (answer == -1) cout << "NO ANSWER!!" << endl; // this array looks like: 5 4 3 2 1 -> no answer!!
else cout << answer<< endl;
}

- wfchiang May 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Idea would be to store the positions (not values) in stack as the value is increasing. Any time value decreases, go through the stack and remove all values higher than current.
So at any point of time, we will have only increasing positions in the stack.
This idea was used to calculate max area under histogram :)

stack s;
s.push(0); cur = arr[0]; int maxdist = 0;
for(int i=1; i< length; i++)
{
   if(arr[i] > cur)
  {
     s.push(i); //push position
      cur = arr[i];
   }
   else
   {
     int cnt = 0;
     while(arr[stack.pop()] > arr[i])
     {
        cnt++;
     }
     //Now push arr[i]
     stack.push(i);
     if(maxdist < cnt)
       maxdist = cnt;
   }
} //end for loop.

//There are items left in stack. Get the difference is positions to see if we have a max
int top = stack.pop(); while(!empty){bottom = stack.pop()};
if((top - bottom) > maxdist) maxdist = top-bottom;

return maxdist;

- Anonymous May 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this logic would not work for A[]={3,7,5,1,2,10}

Ans is 5 but your code will give 3....correct me if I am wrong.

- lesnar56 May 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ans is 10-2=8.
check it please

- Anonymous May 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Answer is 5 not 8. You are asked to calculate the distance between subscript not the values. Max (j - 1) not Max(A[j] - A[i]).

- Guest May 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if it were asked to find out minimum j-i such that A[i] < A[j], it could be solved using stack in O(n) time. But, I doubt for max j-i such algorithm ever exists.

Seems all previous CORRECT solutions takes O(n^2) time - which is trivial. Any idea of O(n logn) solution there?

- anon May 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It can be solved in O(n log n) by constructing Binary Search tree.

- Vimalkumar May 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do you know the complexity of BST? BST may have height O(n) in worst case - that leads O(n^2) complexity. You might use balanced tree (AVL, RB) - which is pretty complex to code.

- anon May 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be solved in O(n) time by using dynamic programing. This is similar to the classic when to sell your share problem. You use the iterative solution of
max[n]=max(0, max(n-1)+(A[j]-A[j-1])). This would give you the differences of each particular day for diff choices of i and j. In a single pass of O(n) you can find the maximum, which is the answer we are looking for. coding this should not be difficult

- Srikanth Kommineni May 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can yo give the code.. i don think it will give a O(n) soln..

- Anonymous May 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

never mind, you didn't understand the problem itself. It asks to find longest index difference, not max difference of value (which is called stock sell problem - simple O(n) solution is there).

- lol May 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in O(n).. Here's how..
Keep two pointers, left and right. Check values pointed by left and right pointers. If the value pointed by right is greater than that pointed by i, store j-i and increment i. Otherwise, decrement j till such a condition occurs. Now, say i has been incremented. If the value pointed by this new i is greater than the one previously pointed by it, simply increment i as in this case j-i can never exceed previously computed j-i. If the value is smaller, then search from current j to the last element.. If such an element is found, update j-i.

- MDRCHD May 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

simply rubbish idea. before posting this type of lame greedy solution, work on paper with few input cases. that way, you'd learn HOW to find counter-example to deny a solution!

- anon May 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void longestContinuousIncrSeq(int* a, int size) {
        int maxstart = 0;
        int max = 1;
        int start = 0;
        for (int i = 1; i < size; i++) {
            if (a[i] > a[i - 1]) {
                if (i - start + 1 > max) {
                    max = i - start + 1;
                   maxstart = start;
                }
           } else {
                start = i;
            }
        }
        cout << "Longest sequence starts at " << maxstart << " and is " << max << " numbers long." << endl;
       for (int i = 0; i < max; i++) {
            cout << a[maxstart + i] << " ";
        }
        cout << endl;
    }

- Ashwini May 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@celicom The logic given by you seems to be working. Do you have any mathematical proof or reference site/book for this logic?

- harry May 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@harry
The sketch of prove:
Lets define function F on two vectors X,Y of the same dimension N as following:
F(X,Y) = max{j-i: X[i] < Y[j]}, then it is easy to see (remember, this is a sketch :-)) that
1) if we create vector B from input vector A as described in the algorithm, then for any vector Z it is true that:
F(A,Z) = F(B,Z)
2) same for the vector C from the algorithm:
for any vector Z it is true that: F(Z,A)=F(Z,C)
So, it follows that F(A,A)=F(B,C). Now it is easy to calculate F(B,C) for a linear time as both B and C are vectors with monotone non-increasing elements...

- celicom June 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can sb explain the question with sample i/p & o/p ..

- WWW June 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

r u blind dude........there are so many samples pasted here

- aaaaaaa December 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey29338" class="run-this">int main() {
int arr[] = {21, 25, 1, 17, 16, 13}
int start = 0, end = 0;
solve(arr, 6, start, end);

cout << "The start point is " << start << " and the end point is " << end
<< endl;
return 0;
}

int solve(int arr[], int len, int& start, int& end) {

int min = 0;
int maxDiff = INT_MIN;

for (int i = 0; i < len; i++) {

if (arr[i] < arr[min])
min = i;

if ((i - min) > maxDiff) {

maxDiff = i - min;
start = min;
end = i;
}
}
return;
}</pre><pre title="CodeMonkey29338" input="yes">by slimboy
</pre>

- Anonymous July 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The above solution solves the problem in O(N)

- slimboy July 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry this solution does not work.

- slimboy July 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@celicom:this is not a o(n) approach.

- shobhit August 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the code. Please correct me if any mistake

void FindMaxDiff(int arr[], int arr_size)
{
int i, first, second;
int diff = 0;
/* There should be atleast two elements*/
if(arr_size < 2)
{
printf(" Invalid Input ");
return;
}
first = second = 0;
for(i = 0; i < arr_size ; i ++)
{
/*If current element is smaller than first then update both first and second */
if(arr[i] > first)
{
second = first;
first = arr[i];
if(diff < (first-second))
diff = (first-second);
}
/* If arr[i] is in between first and second then update second */
else if (arr[i] > second)
{
second = arr[i];
}
}
Printf(“ xxxx “);
}

- Sidhartha February 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually in this case max difference would be 105 100 - (-5) = 105... No???

- Anonymous February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@sidhartha,thanks for quick reply
Can you check you above code on input 2,1,4,100,-5
value of max difference,diff should be 99(100-1)
but your code after loop iteration will give 96.

- rahul baid February 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
one unsorted array is given.Find out the index i and j ,j> i for which a[j] - a[i] is maximum.perform in linear time complexity
*/

bool findLargestDiff(int data[], int size, int &low, int &high)
{
	int tmpLow = 0, tmpHigh = 1;
	
	if(size < 2)
		return false;

	int low = 0, high = 1;
	
	if(size == 2)
	{
		return true;
	}
	
	while(tmpLow < size - 1 && tmpHigh < size)
	{
		if(data[tmpLow] > data[tmpLow+1])  //we try to find the lowest point at first
		{
			tmpLow++;
			if(tmpHigh <= tmpLow) tmpHigh = tmpLow + 1;   //j > i is a requrement 
			
			if(data[tmpHigh] - data[tmpLow] > data[high] - data[low])  //cover {-10, -5, -3} scenario
			{
				low = tmpLow;
				high = tmpHigh;
			}
		}
		else  //the next is biggest than the tmpLow
		{
			while(tmpHigh < size)
			{
				if(data[tmpHigh] > data[tmpLow])
				{
					if(data[tmpHigh] - data[tmpLow] > data[high] - data[low])
					{
						low = tmpLow;
						high = tmpHigh;
					}
					tmpHigh++;
				}
				else  //find a new low 
				{
					tmpLow = tmpHigh;
					tmpHigh++;
					break;
				}
			}
		}
	}
	
	return true;
}

- Ric February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Find min and max element in the array.
2. The diff between them is the max diff.

- bkmn February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Not necessary. You have to maintain j < i property also.

- Mohit Agrawal February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For understanding the solution better i'll the algorithm in two passes at max (still order is O(n)):
In the first pass find out the maximum and minimum elements. If the index of maximum is greater than that of minimum then the problem is solved. Otherwise find:
let min,max be the found minimum and maximum elements respectively.
maximum(diff(minium element that is left to max,max),diff(min,maximum element that is right to min))

If we manage the variables properly we can do it in one pass :)

Eg: 5, 15, 2, 10, 20, 1, 17, 0, 8, 16
Apparently the required indexes are 2,4 (max difference =18)

Now using algo,
minimum element = 0
maximum element = 20
but index of 0 > index of 20
now minimum element left of 20 is 2, difference1 = 18
maximum element right of 0 is 16, difference2 = 16
maximum(difference1, difference2) = 18

Order is O(n) and if we manage variables properly, we can do it in one pass

- SecretAgent February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Will not work for
5,15,3,10,20,1,19,0,8,16
Your also gives 3,20, whereas the answer is 1,19.

- Ashwini February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

'i' will iterate from 0 to n-2 and 'j' from 1 to n-1.
update iLoc and jLoc accordingly. jLoc will contain the largest element in the array and iLoc has smallest. so the difference will be maximum. For the condition i<j we should check if jLoc is greater the 'i' in the iteration.

//takes array as argument and returns an array with iLoc and jLoc
compute smalliLargej(a)
{
   int iLoc = 0;
   int jLoc = 1;
   int smallestI = a[0];
   int largestJ = a[1];
   for(int i = 0, j = 1;j < n;i++,j++)
   {
       if(a[j] > largestJ)
           {
                jLoc = j;
                largestJ = a[j];
           }
       if(a[i] < smallestI && i < jLoc)
          {
                iLoc = i;
                smallestI = a[i];
           }
   }
   int[] temp = {iLoc,jLoc}
   return temp;
}

- feb29 February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//A c# version

void FindMaxDiff(int[] arr, out indx1, out indx2)
{
int len = arr.Length;
int i,j, max, min;
min = arr[0];max = 0;
for (i=0,j=1;j<len;i++,j++)
{
if(arr[i]<arr[j])
{
if(arr[i]<min)
{
min = arr[i];
indx1 = i;
}
if(arr[j]>max)
{
max = arr[j];
indx2 = j;
}
}
}
}

j is always greater than i, since we do not check the conditions for max being i and the rest is finding the max and min simultaneously. 3 comparisons for every 2 values better than 4 comparisons. O(n)
Please let me know if there are errors here

- Struggler February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your ordering will become wrong:
5,15,3,10

your answer will be 3,15 but the i<j is invalid

- tomb February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for pointing this out tomb

- Struggler February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

void FindMaxDiff(int[] arr, out indx1, out indx2)
{
int len = arr.Length;
int i,j, max, min;
min = arr[0];max = 0;
indx1=indx2=0;
for (i=0,j=1;j<len;i++,j++)
{
if(arr[i]<arr[j])
{
if(arr[i]<min&&indx1 < j)
{
min = arr[i];
indx1 = i;
}
if(arr[j]>max&&indx2 >= indx1 )
{
max = arr[j];
indx2 = j;
}
}
}
}

// Indx2>Indx1 may not be required

- Struggler February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in 3 pases
1 pass) Find the minimum till that index for each index and store it an array A
2 pass) Find the maximum till that index for each index but traverse the array in reverse order and store it an array B
3 pass) Find the difference B[i] - A[i] at each index you will get the max difference and from that the indexes

example
input : 5 15 3 10 20 1 19 0 8 16

A : 5 5 3 3 3 1 1 0 0 0
B : 20 20 20 20 20 19 19 16 16 16
diff: -----------17 17 18 18(max) 16 ---------

find indices of 19 and 1 linear solution and simple though there could be better ;)

- Vignesh Miriyala February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

So far among all the solutions, this is the best.
1st pass form A (as shown in soln)
2nd pass form B.
3rd pass find difference. and Also update a MaxDiff parameter.
First occurrence of MaxDiff gives the 'i' value, Last occurrence gives the 'j' .
Brilliant

- Anonymous February 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

So far among all the solutions, this is the best.
1st pass form A (as shown in soln)
2nd pass form B.
3rd pass find difference. and Also update a MaxDiff parameter.
First occurrence of MaxDiff gives the 'i' value, Last occurrence gives the 'j' .
Brilliant

- Anonymous February 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

So far among all the solutions, this is the best.
1st pass form A (as shown in soln)
2nd pass form B.
3rd pass find difference. and Also update a MaxDiff parameter.
First occurrence of MaxDiff gives the 'i' value, Last occurrence gives the 'j' .
Brilliant

- MA February 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Solution doesnt work for an array which is sorted in descending order.
like 7,5,3,2,1
A = 7,5,3,2,1
B = 7,5,3,2,1
Max Diff should have been = -1
but it gives 0
!!!

- pradeepBansal March 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

isn't it the same problem as having the max profit in share price movements of a given date?

- hii February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Question says "perform in linear time complexity" .. I have a doubt cant we use two for loops?

By the way.. Can some one review this solution:

int a[4] = {2,3,1,4,5,1,6,2,3,4};
int n=10;
int ti, tj, maxj, mini, i, j;
i=n-1;j=n-1;
mini=0; maxj=n-1; ti=0;tj=0;
for(int k=0, l=n-1; k<n; k++,l--)
{
if(a[k]>=a[tj])
{
tj=k; ti=mini;
}
else if(a[k]<a[mini]) mini=k;

if(a[l]<=a[i])
{
i=l; j=maxj;
}
else if(a[l]>a[maxj]) maxj=l;
}

if (a[tj]-a[ti] > a[j]-a[i]){ i = ti; j=tj;}


//- -- - -- -- here we re traversing from left to right...
finding the largest a[k] and replacing j=k; if current a[i] > some k which we have already passed through then i== that minimum;

at the same time we are going right to left..
finding smallest a[k] and making i=k; if current a[j] < some k which we have already passed through then j== that max;

then we compare the two differences.. and assign i and j

- ediston February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

List findhighestdifindex(int a[])
{
int minindex=0,maxindex=0,max=0,min=23456;
List indexlist = new ArrayList();
for (int i = 0; i < a.length; i++) {
if(a[i]<min)
{
min=a[i];
minindex=i;
}
}
if(min<a.length)
{
for (int i = minindex+1; i < a.length; i++) {
if(a[i]>max)
{
max=a[i];
maxindex=i;
}
}
}
indexlist.add(maxindex);
indexlist.add(minindex);
return indexlist;
}

- noname February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printMax(int []a){
int min,min1,max,x,x1,y;
min=max=min1=a[0];
x=x1=y=0;
for (int i=1;i<a.length;i++){
if(a[i]>=max){
max=a[i];
y=i;
}
else if(a[i]<min){
min1=a[i];
x1=i;
}
if((a[i]-min1)>(max-min)){
max=a[i];
min=min1;
x=x1;
y=i;
}
}
System.out.println( x);
System.out.println( y);
System.out.println( min);
System.out.println(max);
}


public static void main(String[] args) {
// TODO Auto-generated method stub
//int ar[]=new int[10];
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}

}

- Anonymous February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printMax(int []a){
int min,min1,max,x,x1,y;
min=max=min1=a[0];
x=x1=y=0;
for (int i=1;i<a.length;i++){
if(a[i]>=max){
max=a[i];
y=i;
}
else if(a[i]<min){
min1=a[i];
x1=i;
}
if((a[i]-min1)>(max-min)){
max=a[i];
min=min1;
x=x1;
y=i;
}
}
System.out.println( x);
System.out.println( y);
System.out.println( min);
System.out.println(max);
}


public static void main(String[] args) {
// TODO Auto-generated method stub
//int ar[]=new int[10];
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}

}

- anubhav February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{public static void printMax(int []a){
int min,min1,max,x,x1,y;
min=max=min1=a[0];
x=x1=y=0;
for (int i=1;i<a.length;i++){
if(a[i]>=max){
max=a[i];
y=i;
}
else if(a[i]<min){
min1=a[i];
x1=i;
}
if((a[i]-min1)>(max-min)){
max=a[i];
min=min1;
x=x1;
y=i;
}
}
System.out.println( x);
System.out.println( y);
System.out.println( min);
System.out.println(max);
}


public static void main(String[] args) {
// TODO Auto-generated method stub
//int ar[]=new int[10];
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}
}

- anubhav jain February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{public static void printMax(int []a){
int min,min1,max,x,x1,y;
min=max=min1=a[0];
x=x1=y=0;
for (int i=1;i<a.length;i++){
if(a[i]>=max){
max=a[i];
y=i;
}
else if(a[i]<min){
min1=a[i];
x1=i;
}
if((a[i]-min1)>(max-min)){
max=a[i];
min=min1;
x=x1;
y=i;
}
}
System.out.println( x);
System.out.println( y);
System.out.println( min);
System.out.println(max);
}


public static void main(String[] args) {
// TODO Auto-generated method stub
//int ar[]=new int[10];
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}
}

- anubhav jain February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{public static void printMax(int []a){
int min,min1,max,x,x1,y;
min=max=min1=a[0];
x=x1=y=0;
for (int i=1;i<a.length;i++){
if(a[i]>=max){
max=a[i];
y=i;
}
else if(a[i]<min){
min1=a[i];
x1=i;
}
if((a[i]-min1)>(max-min)){
max=a[i];
min=min1;
x=x1;
y=i;
}
}
System.out.println( x);
System.out.println( y);
System.out.println( min);
System.out.println(max);
}


public static void main(String[] args) {
// TODO Auto-generated method stub
//int ar[]=new int[10];
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}
}

- anubhav jain February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the running code enjoy

{public static void printMax(int []a){
		int min,min1,max,x,x1,y;
		min=max=min1=a[0];
		x=x1=y=0;
		for (int i=1;i<a.length;i++){
			if(a[i]>=max){
				max=a[i];
				y=i;
			}
			else if(a[i]<min){
				min1=a[i];
				x1=i;
			}
			if((a[i]-min1)>(max-min)){
				max=a[i];
				min=min1;
				x=x1;
				y=i;
			}
		}
		System.out.println( x);
		System.out.println( y);
		System.out.println( min);
		System.out.println(max);
		}
		
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//int ar[]=new int[10];
		int ar[]={5,15,3,10,20,1,19,0,8,16};
		printMax(ar);
System.out.write(1);
	}

}

- anubhav jain February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The below code is working. Let me know if you see any issues
{

public class MaxMin {

public static void main(String[] args) {
int [] arr = {25, 15, 3, 10, 20, 3, 19, 5, 8, 21};
int y=0;
int i=0;
int j = 1;
while(arr[y]>arr[y+1])
y++;
int max = arr[y];
int min = arr[y+1];
int tmpi=y;
int tmpj=y+1;
int tmpMax =arr[y+1];
int tmpMin = arr[y];
boolean findMin=false,findMax=false;
for(int x = y+1; x <arr.length;x++){
if((arr[x] < min && arr[x] < tmpMin) || (findMax && tmpMax - arr[x] > max - min)){
tmpMin = arr[x];
tmpi=x;
findMin = true;
findMax = false;
}
if((arr[x] > max && arr[x] > tmpMax) || (findMin && arr[x] - tmpMin > max - min))
{
tmpMax = arr[x];
tmpj = x;
findMin = false;
findMax = true;

}
if(max - min < tmpMax - tmpMin && tmpj > tmpi){
max = tmpMax;
min = tmpMin;
i=tmpi;
j=tmpj;
}
}
System.out.println(i + " " + j);
}

}

}

- Ashwini February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int maxDiff( int* numbers, int size ) {
int max_diff = 0;
int min_ind = 0;
for( int i = 0 ; i < size; i++ ) {

if( numbers[i] < numbers[min_ind] ) {
min_ind = i;
}
else {
if ( ( numbers[i] - numbers[min_ind] ) > max_diff ) {
max_diff = numbers[i] - numbers[min_ind] ;
}
}
}

return max_diff;
}

- Anil February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

int finddiff(int *A, int len) {

int min = A[o];
int max = A[len-1];
int diff = 0;

int i = 0;
int j = len-1;

while( i <=j ) {
if(A[i] < min) { min = A[i]; }
if(A[j] > max) { max = A[j]; }
if( A[i] > A[j]) { j--; continue; }
if( diff < (max - min))
diff = max - min;

i++;
}

return diff;
}

int main() {

int A[] = { 2, 5, 10, -2, 27, 13, 24, -1};
int maxdiff = finddiff(A, 8);
cout << "Max diff = " << maxdiff << endl;

}




}


}

- Prathi February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

int finddiff(int *A, int len) {

int min = A[o];
int max = A[len-1];
int diff = 0;

int i = 0;
int j = len-1;

while( i <=j ) {
if(A[i] < min) { min = A[i]; }
if(A[j] > max) { max = A[j]; }
if( A[i] > A[j]) { j--; continue; }
if( diff < (max - min))
diff = max - min;

i++;
}

return diff;
}

int main() {

int A[] = { 2, 5, 10, -2, 27, 13, 24, -1};
int maxdiff = finddiff(A, 8);
cout << "Max diff = " << maxdiff << endl;

}




}


}

- Prathi February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dynamic programming
{
int i,j,index,min,max;
min=max=i=j=0;
for (index=1; index<size; index++) {
if (a[index]>a[j]) {
j=index;
if (a[j]-a[i]>a[max]-a[min]) {
max=j;
min=i;
}
}
if (a[index]<a[i]) {
i=j=index;
}
}
}

- Miranda February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. minimumIn[1...i] = min(a[i], minimum[1...i-1]); O(n) time and space, left to right
2. maximumIn[n...i] = max(a[i], maximum[n...i+1]); O(n) time and space, right to left
3. find i, for which maximumIn[n...i] - minimumIn[1...i] is maximum, again O(n) time, no extra space

- Sajal February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take two variables
min and maxdiff,
Keep track of min element found so far and take difference of current element and the min value found so far. keep storing difference in the maxdiff variable.

at the end it will return the max differnce.
and for index keep there track too.

- Anonymous February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

very nice solution

- Anonymous February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void arrayFindSubMax(int *a,int length,int *i,int *j)
{
	int max=0,sub,p,q;
	*i=0;
	*j=0;
	for(p=0,q=1;q<length;)
	{
		sub = a[q] - a[p];
		if(sub>max)
		{
			max = sub;
			*i = p;
			*j = q;
		}
		if(sub>0) q++;
		else {p=q;q++;}
	}
}

- yingdi1111 February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

int main()
{

int array[5] = {10,4,2,-7,-1};
int i,j,count,min,max,result;

i=j=0;

min = array[0];
max = array[0];

for(count=1;count<5;count++)
{
if(min > array[count])
{
min = array[count];
i = count;
}

if(max < array[count])
{
max = array[count];
j=count;
}

}

printf("Min %d - %d\n",i,min);
printf("Max %d - %d\n",j,max);
result = max-min;
printf("Result of max and min -%d",result);
return 0;
}

- Anonymous February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Main
{
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args)
    {
        // TODO code application logic here
//        int values[] = {3, 5, 1, 2}; int expected[] = {0, 1};
//        int values[] = {5, 15, 3, 10, 20, 1, 19, 0, 8, 16};  int expected[] = {5, 6};
//        int values[] = {7, 5, 4, 3, 1, 6}; int expected[] = {4, 5};
//        int values[] = {5, 15, 2, 10, 20, 1, 17, 0, 8, 16}; int expected[] = {2, 4};
//        int values[] = {5, 15, 3, 10, 20, 1, 19, 0, 8, 16}; int expected[] = {5, 6};
//        int values[] = {5, 15, 3, 10}; int expected[] = {0, 1};
//        int values[] = {2, 3, 1, 4, 5, 1, 6, 2, 3, 4}; int expected[] = {2, 6};
//        int values[] = {25, 15, 3, 10, 20, 3, 19, 5, 8, 21}; int expected[] = {2, 9};
//        int values[] = { 2, 5, 10, -2, 27, 13, 24, -1}; int expected[] = {3, 4};
//        int values[] = {10, 4, 2, -7, -1}; int expected[] = {3, 4};
//        int values[] = {4, 10, 2, -7, -1}; int expected[] = {0, 1};
        indices(values, expected);
    }

    /**
     * one unsorted array is given.  Find out the index i and j, j > i for
     * which a[j] - a[i] is maximum.  perform in linear time complexity.
     *
     * @param values
     * @param expected
     * @return
     */
    public static final int[] indices(final int[] values, final int[] expected)
    {
//        int values[] = {3, 5, 1, 2}; int expected[] = {0, 1};
//        int values[] = {5, 15, 3, 10, 20, 1, 19, 0, 8, 16};  int expected[] = {5, 6};
//        int values[] = {7, 5, 4, 3, 1, 6}; int expected[] = {4, 5};
//        int values[] = {5, 15, 2, 10, 20, 1, 17, 0, 8, 16}; int expected[] = {2, 4};
//        int values[] = {5, 15, 3, 10, 20, 1, 19, 0, 8, 16}; int expected[] = {5, 6};
//        int values[] = {5, 15, 3, 10}; int expected[] = {0, 1};
//        int values[] = {2, 3, 1, 4, 5, 1, 6, 2, 3, 4}; int expected[] = {2, 6};
//        int values[] = {25, 15, 3, 10, 20, 3, 19, 5, 8, 21}; int expected[] = {2, 9};
//        int values[] = { 2, 5, 10, -2, 27, 13, 24, -1}; int expected[] = {3, 4};
//        int values[] = {10, 4, 2, -7, -1}; int expected[] = {3, 4};
//        int values[] = {4, 10, 2, -7, -1}; int expected[] = {0, 1};
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int minIndex = 0;
        int maxIndex = 0;
        int retMinIndex = 0;
        int retMaxIndex = 0;
        int maxDiff = 0;

        for(int i = 0; values.length > i; ++i)
        {
            if(min > values[i])
            {
                min = values[i];
                minIndex = i;

                // takes care of j > i constraint
                max = values[i];
                maxIndex = i;
            }
            else if(max < values[i])
            {
                max = values[i];
                maxIndex = i;
            }
            
            if(max - min > maxDiff)
            {
                maxDiff = max - min;
                retMinIndex = minIndex;
                retMaxIndex = maxIndex;
            }

            System.out.println("diff: " + (max - min));
        }

        int answer[] = new int[]{retMinIndex, retMaxIndex};

        System.out.println("answer: " + Arrays.toString(answer));
        System.out.println("expected: " + Arrays.toString(expected));

        return answer;
    }

- Anonymous February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findMaxDiffPosition(int element[], int n, int& firstElementPos, int& lastElementPos)
{
int diff = element[1] - element[0];
int i,j;

i = 0;
j = 1;

while( i < n && j < n)
{
if (element[i] < element[j])
{
if ( (element[j] - element[i] ) > diff )
{
firstElementPos = i;
lastElementPos = j;
diff = element[j] - element[i];
}
j++;
}
else
{
i = j;
j = i + 1;
}
}
return diff;
}

- Sachin February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>

void find_i_j(int a[], int n) {
	int i, j, k, minval, maxdiff;
	i=j=k=maxdiff=0;
	minval=a[0];

	for (k=1; k<n; k++) {
		 
		if (minval > a[k]) {
			minval=a[k];
			i=k;
			continue;
		}
		if ((a[k]-minval) > maxdiff) {
			maxdiff=a[k]-minval;
			j=k;
		}	
	}
	printf("i %d, val %d\nj %d, val %d\n", i+1, a[i], j+1, a[j]);
	
}

int main(void) {

	int a[10];
	int i;

	for (i=0;i<10;i++)
		scanf("%d",&a[i]);

	for (i=0;i<10;i++)
		printf("%d, ",a[i]);
	printf("\n");

	find_i_j(a, 10);
	return 0;
}

- Anonymous February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>

void find_i_j(int a[], int n) {
	int i, j, k, minval, maxdiff;
	i=j=k=maxdiff=0;
	minval=a[0];

	for (k=1; k<n; k++) {
		 
		if (minval > a[k]) {
			minval=a[k];
			i=k;
			continue;
		}
		if ((a[k]-minval) > maxdiff) {
			maxdiff=a[k]-minval;
			j=k;
		}	
	}
	printf("i %d, val %d\nj %d, val %d\n", i+1, a[i], j+1, a[j]);
	
}

int main(void) {

	int a[10];
	int i;

	for (i=0;i<10;i++)
		scanf("%d",&a[i]);

	for (i=0;i<10;i++)
		printf("%d, ",a[i]);
	printf("\n");

	find_i_j(a, 10);
	return 0;
}

- C February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

have an array which is the same size as original
Initialize elements to ZERO


max_so_far = 0;

Start from the end (i = n-1; i >= 0; i--)
{
if (max_so_far > a[i])
{
max_so_far = a[i]
}
else
{
scan[i] = max_so_far-a[i];
}
}

max_so_far = scan[0];
int idx_min = 0;
for (i = 1 -> n-1)
{
if (max_so_far < scan[i])
{
max_so_far = scan[i]
idx_min = i;
}
}

// idx_min has the value which is an the min in subtraction

int to_find = scan[idx_min] + a[idx_min];
int idx_max = 0;
for(i = idx+1 -> n-1)
{
if (to_find == a[i])
{
idx_max = i;
break
}
}


// now idx_min has the min and idx_max has the max
a[idx_max] - a[idx_min] - should give the max diff

- bkmn February 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Pair<Integer, Integer> findMaxDiffIndices(int[] a) {
    Pair<Integer, Integer> p = new Pair<Integer, Integer>(0, 0);
    int i = 0;
    int j = 0;
    int cmin = 0;
    for (int k = 1; k < a.length; k++) {
      if (a[k] < a[i]) {
        cmin = k;
      } else if (a[k] - a[cmin] > a[j] - a[i]) {
        j = k;
        i = cmin;
      }
    }
    p.fst = i;
    p.snd = j;
    return p;
}

- amshali February 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int min, max, contendermin;
min = max = contendermin = -1;
for( int i=0; i<n; i++ )
{
if( min == -1 && max == -1 )
min = i;
else
{
if( a[min] > a[i] )
if( max == -1 )
min = i;
if( contendermin == -1 || a[contendermin] > a[i] )
contendermin = i;
else if( max == -1 )
max = i;
else if( a[max] < a[i] )
{
max = i;
if( contendermin != -1 )
{
min = contendermin;
contendermin = -1;
}
}
}
}

- y2km11 February 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int min, max, contendermin;
min = max = contendermin = -1;
for( int i=0; i<n; i++ )
{
	if( min == -1 && max == -1 )
		min = i;
	else
	{
		if( a[min] > a[i] )
			if( max == -1 )
				min = i;
			if( contendermin == -1 || a[contendermin] > a[i] )
				contendermin = i;
		else if( max == -1 )
			max = i;
		else if( a[max] < a[i] )
		{
			max = i;
			if( contendermin != -1 )
			{
				min = contendermin;
				contendermin = -1;
			}
		}
	}
}

- y2km11 February 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int min, max, contendermin;
min = max = contendermin = -1;
for( int i=0; i<n; i++ )
{
	if( min == -1 && max == -1 )
		min = i;
	else
	{
		if( a[min] > a[i] )
			if( max == -1 )
				min = i;
			if( contendermin == -1 || a[contendermin] > a[i] )
				contendermin = i;
		else if( max == -1 )
			max = i;
		else if( a[max] < a[i] )
		{
			max = i;
			if( contendermin != -1 )
			{
				min = contendermin;
				contendermin = -1;
			}
		}
	}
}

- y2km11 February 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just a thought :- Can we use max-heap and min-heap to do it in linear time.

We can create min or max heap in linear time.

Comments Please.

- Free Bird February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

using namespace std;
#define NUMBER 10
int main(){

int a[NUMBER] = {5, 15, 3, 10, 20, 1, 19, 0, 8, 16};

int minElement = a[0];
int maxDiff = a[1]-a[0];
int index1 = 0, index2 = 1, currDiff;

for(int i = 1; i<NUMBER; i++){
if(a[i] < minElement){
minElement = a[i];
currDiff = maxDiff;
}else{
currDiff = a[i] - minElement;
}
if(currDiff > maxDiff){
maxDiff = currDiff;
index2 = i;
}
}

minElement = a[index2] - maxDiff;

for(int i = 0; i<index2; i++){
if(a[i] == minElement){
index1 = i;
break;
}
}

cout<<"Maximum Diff is: "<<maxDiff<<endl;
cout<<"Index of min element and max element are : "<<index1<<" "<<index2<<endl;
system("pause");

return 0;
}

- sbh February 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void main()
{
int a[]= {3, 5, 1, 2};
int MAX=0, i=0, j=0, m,t=0,b=0;
m= sizeof(a)/ sizeof(int);

for(j=1;j<m;j++)
{
if(a[j]>a[i])
{
if(a[j]-a[i]> MAX)
{
t=j;
b=i;
MAX= a[j]-a[i];
}
}
else
i=j;
}

printf("%d,%d,%d",MAX,b,t);
return;
}

- Anonymous May 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void main()
{
int a[]= {15,13,11,7,4,0,-1};
int MAX=0, i=0, j=0, m,t=0,b=0;
m= sizeof(a)/ sizeof(int);

for(j=1;j<m;j++)
{
if(a[j]>a[i])
{
if(a[j]-a[i]> MAX)
{
t=j;
b=i;
MAX= a[j]-a[i];
}
}

else if(a[j]==a[i])
continue;

else
i=j;
}

if(MAX==0)
{
i=1;
MAX=a[1]-a[0];
b=0;
t=1;
for(j=2;j<m;j++)
{
if(a[j]-a[i]> MAX)
{
MAX= a[j]-a[i];
b=i;
t=j;
}
else
i=j;
}
}

printf("%d,%d,%d",MAX,b,t);
return;

}

- Anonymous May 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
  int size,curr,curr_id,min_id,max_id,diff;  
  printf("Enter the size of array : ");
  scanf("%d",&size);
  int *arr=(int*)malloc(sizeof(int)*size);
  int i=0;
  for(i=0;i<size;i++)
  {
          scanf("%d",&arr[i]);
  }
  max_id=1;
  min_id=0;
  diff=arr[1]-arr[0];
  curr=arr[1];
  curr_id=1;
  if(arr[1]>arr[0])
  {
                   curr=arr[0];
                   curr_id=0;
  }
  for(i=2;i<size;i++)
  {
                  if(arr[i]-curr >= diff)
                  {
                           diff=arr[i]-curr;
                           min_id=curr_id;
                           max_id=i;     
                  }
                  if(arr[i]<curr)
                  {
                            curr=arr[i];
                            curr_id=i;
                  } 
  }
  printf("Max diff is %d\n",diff);
  printf("Min index value is %d\n",min_id);
  printf("Max index value is %d\n",max_id);
  system("PAUSE");	
  return 0;
}

- Lavish Goel June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think taking additional space this problem can be solved in O(n).
1) Pass through the array and create another array which holds the value of the differences of two adjacent elements.
b[i]=a[i+1]-a[i]
2) Find the maximum sub array sum for array b, which can be found in O(n) time. For any sub array sum as the answer b[l] to b[r] the value will actually be a[l+1]-a[l]+a[l+2]-a[l+1]...a[r+1]-a[r]. which reduces to a[r+1]-a[l] where r+1>l and this the maximum such value.

- Random July 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import sys

A = [int(n) for n in sys.stdin.read().strip().split()]
i, j = 0, 1
mini = 0
minup2n = A[mini]
n = 2
while n < len(A):
  if A[n - 1] < minup2n:
    mini = n - 1
    minup2n = A[mini]
  if A[n] - minup2n > A[j] - A[i]:
    i = mini
    j = n
  n = n + 1

print 'A[%d] = %d, A[%d] = %d' % (i, A[i], j, A[j])

- Mansour March 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int minCandidate = 0;
i = 0;
j = 0;
for (int k = 1; k < a.Length; k++)
{
    if (a[k] > a[j])
    {
        j = k;
    }
    else if (a[k] < a[minCandidate])
    {
        minCandidate = k;
    }

    if (j > minCandidate && a[j] - a[minCandidate] > a[j] - a[i])
    {
        i = minCandidate;
    }
    if (a[j] - a[i] < a[k] - a[minCandidate])
    {
        i = minCandidate;
        j = k;
    }
}

- Manoj Agarwal April 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void MaxDifference(int[] a) {
		if(a.length == 0){
			System.out.println("Empty Array");
		}
			
		int i = 0, minIndex = 0;
		int j = a.length - 1, maxIndex = a.length - 1;
		int maxDiff = a[j] - a[i];
		int count = 0;
		while(count < a.length - 1){
			if(a[maxIndex] - a[i+1] > maxDiff && a[i+1] < a[minIndex] && maxIndex > i+1){
				minIndex = i+1;
				maxDiff = a[maxIndex] - a[minIndex];
			}
			if(a[j - 1] - a[minIndex] > maxDiff && a[j-1] > a[maxIndex] && minIndex < j-1){
				maxIndex = j-1;
				maxDiff = a[maxIndex] - a[minIndex];
			}
			i++;j--;count++;
			System.out.println("count :" + (count) + " difference : " + maxDiff + "  min value " + a[minIndex] + " max value " + a[maxIndex]);
		}
		System.out.println("difference : " + maxDiff + "  min value " + a[minIndex] + " max value " + a[maxIndex]);
		
	}

- coffee break April 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Correct me if I am wrong

Algo:
i = 0, j = size-1

while(i<j)
{
while (a[i]> a[i+1]) i++
while (a[j]<a[j-]) j--;
if a[j]-a[i] > maxdiff
overwrite maxdiff
}

- Logan September 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Correct me if I am wrong

Algo:
i = 0, j = size-1

while(i<j)
{
while (a[i]> a[i+1]) i++
while (a[j]<a[j-]) j--;
if a[j]-a[i] > maxdiff
overwrite maxdiff
}

- Logan September 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here the no at index j has to be the maximum element of the array and no at index i has to be the minimum. So we can have 4 variables max, min, maxIndex and minIndex. Initially max=min=A[0] and maxIndex=minIndex=0. In linear time, traverse the array and find the minimum and maximum nos and return their corresponding indices.

- pnkapadia6 May 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void FindMaxDiffIndices(int[] array)
{
    int min = Int32.MaxValue;
    int max = Int32.MinValue;
    int max_i = 0, min_i = 0;
    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] < min)
        {
            min = array[i];
            min_i = i;
        }
        if (array[i] > max)
        {
            max = array[i];
            max_i = i;
        }
    }
    if (max_i > min_i)
        Console.WriteLine("{0}, {1}", min_i, max_i);
    else
    {
        int min1 = Int32.MaxValue;
        int min1_i = 0;
        for (int i = 0; i < max_i; i++)
        {
            if (array[i] < min1)
            {
                min1 = array[i];
                min1_i = i;
            }
        }
        int max1 = Int32.MinValue;
        int max1_i = min_i;
        for (int i = min_i; i < array.Length; i++)
        {
            if (array[i] > max1)
            {
                max1 = array[i];
                max1_i = i;
            }
        }
        if (max - min1 > max1 - min)
        {
            Console.WriteLine("{0}, {1}", min1_i, max_i);
        }
        else
        {
            Console.WriteLine("{0}, {1}", min_i, max1_i);
        }
    }
}

- ShaRai August 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void FindMaxDiffIndices(int[] array)
{
    int min = Int32.MaxValue;
    int max = Int32.MinValue;
    int max_i = 0, min_i = 0;
    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] < min)
        {
            min = array[i];
            min_i = i;
        }
        if (array[i] > max)
        {
            max = array[i];
            max_i = i;
        }
    }
    if (max_i > min_i)
        Console.WriteLine("{0}, {1}", min_i, max_i);
    else
    {
        int min1 = Int32.MaxValue;
        int min1_i = 0;
        for (int i = 0; i < max_i; i++)
        {
            if (array[i] < min1)
            {
                min1 = array[i];
                min1_i = i;
            }
        }
        int max1 = Int32.MinValue;
        int max1_i = min_i;
        for (int i = min_i; i < array.Length; i++)
        {
            if (array[i] > max1)
            {
                max1 = array[i];
                max1_i = i;
            }
        }
        if (max - min1 > max1 - min)
        {
            Console.WriteLine("{0}, {1}", min1_i, max_i);
        }
        else
        {
            Console.WriteLine("{0}, {1}", min_i, max1_i);
        }
    }
}

- ShaRai August 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
One unsorted array is given.Find out the index i and j ,j> i for which 
a[j] - a[i] is maximum.perform in linear time complexity.
*/

#include<iostream>
using namespace std;

int main()
{
    int arr[] = {1, 12, 3, 6, 2, 8, 17, 9, 1};
//    int arr[] = {7, 5, 2};
    int size = sizeof(arr)/sizeof(*arr);
    
    int tillMin = arr[0];
    int tillMax = arr[1];    
    int diff = tillMax-tillMin;
    int valI=0, valJ = 1;    
    for(int i=2;i<size;i++)
    {
        if(diff < arr[i]-tillMin)
            diff = arr[i]-tillMin;
        
        if(arr[i] > tillMax)
        {
            valJ = i;
            tillMax = arr[i];
        }
        else if(arr[i] < tillMin)
        {
            valI = i;
            tillMin = arr[i];
        }
    }
    
    cout<<"  Maximum difference is :- "<<diff<<"  i = "<<valI<<"  j = "<<valJ<<endl;
    system("PAUSE");
    return 0;
}

- skum July 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
One unsorted array is given.Find out the index i and j ,j> i for which 
a[j] - a[i] is maximum.perform in linear time complexity.
*/

#include<iostream>
using namespace std;

int main()
{
    int arr[] = {1, 12, 3, 6, 2, 8, 17, 9, 1};
//    int arr[] = {7, 5, 2};
    int size = sizeof(arr)/sizeof(*arr);
    
    int tillMin = arr[0];
    int tillMax = arr[1];    
    int diff = tillMax-tillMin;
    int valI=0, valJ = 1;    
    for(int i=2;i<size;i++)
    {
        if(diff < arr[i]-tillMin)
            diff = arr[i]-tillMin;
        
        if(arr[i] > tillMax)
        {
            valJ = i;
            tillMax = arr[i];
        }
        else if(arr[i] < tillMin)
        {
            valI = i;
            tillMin = arr[i];
        }
    }
    
    cout<<"  Maximum difference is :- "<<diff<<"  i = "<<valI<<"  j = "<<valJ<<endl;
    system("PAUSE");
    return 0;
}

- skum July 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int i=0;
int j=n-1;

while(i!=j)
{
	if (A[i] < A[j])
	{
		cout<<j<<i;
		break;
	}	
	else if (A[i] < A[j-1])
	{	
		cout<<j-1<<i;
		break;
	}
	else if (A[i+1] < A[j])
	{
		cout<<j<<i+1;
		break;
	}
	else
	{
		i++;
		j--;
	}
}

- camSun May 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It won't wok for all cases....if required pair falls within first half or second half.

Consider the example,
5 6 7 8 9 4 3 2 1 0

- Vimalkumar May 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

although it works for ur example...i agree it would work for all cases.

a O(nlogn) solution would be to divide the array into 2 euqal halfs and recurse on those half and also check if i lie in the first part and j lies in the second part.
the running time owudl be T(n) = 2T(n/2) + n
therefore O(nlogn)

could anyone think of O(n) solution?

- camSun May 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@amit: your greedy approach SUCKS! it's not correct ever.

Your recurrence is also wrong. It'd be T[n] = 2T[n/2]+O(n^2) => leads O(n^2) solution. The merge step needs to compare each of left half against each of right half to see which (j-i) is largest.

- anon May 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I like this solution. Even I got the same idea, it is o(n) and i guess it is working for all possible inputs that i tried so far. Can anybody please tell whether it is failing for any example.

- SS May 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ur solution will fail at this 5 6 7 6 2 3

- @amit June 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

is there any trick?i feel this simple enough. Pls correct if wrong

for(i=0;j=A.length-1;j>=0;i++,j--)
  if(A[i]<A[j]){
    print(j-i)
    break
  }

- Sathya May 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry, it won't work.when you r comparing A[i], A[j] if A[i]>A[j] then you are moving both i and j.in that case it may happen like A[i+1]>A[j-1] but there may be possibility that A[i+1]<A[j] or A[i]<A[j-1] .In both of these cases the difference in indexes is j-(i+1) and (j-1)-i. that means j-i-1 which is bigger than (j-1)-(i+1). that is j-i-2.

- putta.sreenivas May 09, 2011 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More