## Amazon Interview Question for Developer Program Engineers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
21
of 23 vote

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

``````private void MaxDiff(int[] a)
{
int min = a; // 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);
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Well done !

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;
}``````

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]);

}``````

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; // 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;
}
}

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

will not work for : 3 5 1 2

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;
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;
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}``````

}

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

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

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

Comment hidden because of low score. Click to expand.
0
of 0 votes

int maxDiff(int arr[], int arr_size)
{
int max_diff = arr - arr;
int min_element = arr;
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;
}

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 = {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;
}

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 = A;
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...

Comment hidden because of low score. Click to expand.
0
of 0 votes

cool idea!

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}

Comment hidden because of low score. Click to expand.
0
of 0 votes

excellent!!

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;"

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]

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.

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,2,7,9,0,3,1,1,1,1};
1) B = {10,2,2,2,0,0,0,0,0,0};
2) C = {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;

Comment hidden because of low score. Click to expand.
0
of 0 votes

nice one !!

Comment hidden because of low score. Click to expand.
1
of 1 vote

A = {20,30,2,11,12,10,1,4};
1) B = {20,20,2,2 ,2 ,2 ,1,1};
2) C = {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

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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.

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.

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?

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;
}

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

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;
}

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

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) 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;
}

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; 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;``````

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

ans is 10-2=8.
check it please

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]).

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?

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.

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.

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

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..

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).

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.

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!

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;
}``````

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?

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...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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>

Comment hidden because of low score. Click to expand.
0
of 0 votes

The above solution solves the problem in O(N)

Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry this solution does not work.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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 “);
}

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???

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.

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;
}``````

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

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

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.

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;
int largestJ = a;
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;
}``````

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;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

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

Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for pointing this out tomb

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;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

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 ;)

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

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

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

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
!!!

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?

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 = {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

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;
}

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;
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;
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}

}

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;
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;
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}

}

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;
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;
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}
}

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;
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;
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}
}

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;
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;
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}
}

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;
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;
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}``````

}

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);
}

}

}

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;
}

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;

}

}

}

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;

}

}

}

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;
}
}
}

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

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

very nice solution

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++;}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

int main()
{

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

i=j=0;

min = array;
max = array;

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;
}

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;
}``````

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 - element;
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;
}

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;

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;
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;
}``````

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;

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;
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;
}``````

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;
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

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;
}``````

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;
}
}
}
}

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;
}
}
}
}``````

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;
}
}
}
}``````

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.

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;
int maxDiff = a-a;
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;
}

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;
}

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-a;
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;

}

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-arr;
curr=arr;
curr_id=1;
if(arr>arr)
{
curr=arr;
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;
}``````

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.

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])``````

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;
}
}``````

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]);

}``````

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
}

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
}

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 and maxIndex=minIndex=0. In linear time, traverse the array and find the minimum and maximum nos and return their corresponding indices.

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);
}
}
}``````

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);
}
}
}``````

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;
int tillMax = arr;
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;
}``````

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;
int tillMax = arr;
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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python3
if a[j] - a[i] isn't abs:

_input = [9, 3, 4, 0, 5, 7, 4, 2, 1, 6]
i_index = _input.index(min(_input))
j_index = _input.index(max(_input[i_index:]))
print (i_index, j_index)

From looking at other people's comments, I get the sense that a[j] - a[i] is abs.

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--;
}
}``````

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

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?

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.

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.

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

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
}``````

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.

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