Amazon Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
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;
}
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]);
}
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;
}
}
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.
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);
}
}
It doesn't work when the first element is the largest of the array, for example: 7,5,4,3,1,6
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
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
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;
}
#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;
}
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...
explain your logic... i didn't understand how it will work for the input - {20,30,2,11,12,10,1,4}
Elegant idea
One small fix, should be B[i] <= C[j] in
"while(B[i] < C[j] && j<N) j=j+1;"
@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]
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,
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;
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
It looks good. But I don't understand the philosophy behind this idea.... Could you please explain the meaning of B and C?? Thanks.
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.
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.
Can you explain it in proper way with an example.. the solution seems to be confusing.., and not getting what you are doing?
#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;
}
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
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;
}
/*
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;
}
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;
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.
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?
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
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.
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;
}
@celicom The logic given by you seems to be working. Do you have any mathematical proof or reference site/book for this logic?
@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...
<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>
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 “);
}
/*
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;
}
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
'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;
}
//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
your ordering will become wrong:
5,15,3,10
your answer will be 3,15 but the i<j is invalid
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
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 ;)
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
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
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
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
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;
}
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);
}
}
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);
}
}
{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);
}
}
{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);
}
}
{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);
}
}
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);
}
}
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);
}
}
}
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;
}
#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;
}
}
}
#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;
}
}
}
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.
#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;
}
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;
}
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;
}
#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;
}
#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;
}
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
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;
}
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;
}
}
}
}
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;
}
}
}
}
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;
}
}
}
}
#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;
}
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;
}
#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;
}
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.
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])
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;
}
}
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]);
}
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.
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);
}
}
}
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);
}
}
}
/*
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;
}
/*
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;
}
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--;
}
}
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
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?
@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.
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.
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
}
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.
A Simple and cleaner solution. No need to check for index j > i etc.
- sk February 19, 2012