5

That's the interview question that I failed back in the days. Nobody of my friends knows where the mistake is and why I've been told that I failed. That's why I decided to ask you to correct my solution Given an array of N integers. An integer K divides array into two subarrays. 

 Left part: A[0], A[1]...A[K]; Right part: A[K+1], A[K+2]... A[N-1];

Need to find the max possible absolute difference of max values in every subarray.

 MaxDiff = Math.Abs(Max(A[0], A[1]...A[K]) - Max(A[K+1], A[K+2]... A[N-1])) Example 1: [1, 3, -3]. If K=1, max difference is |3-(-3)| = 6. Example 2: [4, 3, 2, 5, 1, 1]. If K=3, max difference is |5 - 1| = 4.

Time and space complexity should be O(n). As I see space complexity of my solution is not O(n) already..

int getMaxDifference(int[]A){ int [] leftMax = new int [A.length]; int [] rightMax = new int [A.length]; int max1 = Integer.MIN_VALUE; int max2 = Integer.MIN_VALUE; int dif = 0; int maxDif = 0; for (int i = 0; i< A.length; i++){ if (A[i]>max1) {max1 = A[i];} leftMax[i] = max1; } for (int j = A.length-1; j>0; j--){ if (A[j]>max2) {max2 = A[j];} rightMax[j] = max2; } for (int k = 0; k<A.length; k++){ dif = Math.abs(leftMax[k] - rightMax[k]); if (dif>maxDif) {maxDif = dif;}} return maxDif; }
Improve this question
4
  • 2
    The space complexity looks O(n) to me... Commented Nov 23, 2017 at 20:37
  • 2
    Need to find the max possible absolute difference of max values in every subarray is that how the question was phrased? Max difference of the max values doesn't really make sense as there's only one option, maybe the question was the max difference or smt similar. Commented Nov 23, 2017 at 21:01
  • Why is "absolute" in the question? There is only 1 max value of each array, so what do you mean by "find the max absolute difference"? To my thinking, a more interesting question would be "what is the maximum absolute difference between any two elements from the 2 arrays"; are you sure that is not the question? Commented Nov 23, 2017 at 21:01
  • 1
    Probably in the second loop you don't include index 0? for (int j = A.length-1; j>=0; j--) Commented Nov 23, 2017 at 21:20

3 Answers 3

Reset to default
2

In your program:

leftMax[k] holds the greatest value in A[0],...,A[k]. rightMax[k] holds the greatest value in A[k],...,A[n-1].

However, the right part should start at index k+1, not at k.

Therefore I suggest you change this part:

for (int k = 0; k<A.length; k++){ dif = Math.abs(leftMax[k] - rightMax[k]); if (dif>maxDif) { maxDif = dif; } }

to

for (int k = 0; k<A.length - 1; k++){ dif = Math.abs(leftMax[k] - rightMax[k + 1]); if (dif>maxDif) { maxDif = dif; } }

In other words, the requirement is to compute:

Math.Abs(Max(A[0], A[1]...A[K]) - Max(A[K+1], A[K+2]... A[N-1]))

but I believe your current program computes:

Math.Abs(Max(A[0], A[1]...A[K]) - Max(A[k], A[K+1], A[K+2]... A[N-1]))
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Could you please explain me your logic? I mean my idea is that at every K-point we will check the difference between 2 values that are:
max value on the right and max value on the left side at certain point. I'm not sure I should compare K and K+1. As every max-array already represents max value at K point, no? I mean maybe I need to change the way I build these max arrays, not the way I find max difference? Any ideas also why I've been told that performance of my method is poor despite that it has O(n) time and space complexity?
I've added some more explanation as to why I think K+1 should be used. One simple way of halving the space complexity is to combine the loop that makes leftmax loop and the loop that uses it. This means that you can avoid creating the leftmax array because you can directly uses max1 instead.
2

The problem is in the Difference Calculation:
If the Input Array is {4,3,2,5,1,1}
Then the Left Array becomes : {4,4,4,5,5,5}
And the Left Array becomes : {5,5,5,5,1,1}

To Calculate the Difference you should compute the difference at kth index of array leftMAX and (k+1)th index of array rightMax .

i.e. for SubArray {4,3,2,5} consider leftMax's subArray {4,4,4,5} and for SubArray {1,1} consider rightMax's subArray {1,1}

i.e. for SubArray {4,3,2,5} and {1,1} the calculation should be between 3rd Index of leftMax and 4th index of rightMax.

Hence Code becomes

for (int k = 0; k<A.length-1; k++){ dif = Math.abs(leftMax[k] - rightMax[k+1]); if (dif>maxDif) {maxDif = dif;}}

Please note that the rightmost element of leftMax and leftmost element of rightMax doesn't gets included in the calculation.

Improve this answer

1 Comment

Yes, Peter de Rivaz has provided the same explanation earlier, too. It looks like you're both right.
1

I'm pretty sure you misinterpreted the question, which was actually "find the maximum absolute difference between any two elements of the 2 arrays".

The answer would require you to find both the max and min elements of each array, then chose the greatest of the absolute of either mina - maxb or maxa - minb.

There is a trivial one-pass O(n) solution that finds both the max and min of each array.

The introduction of K is mostly irrelevant, and possibly a red herring. There are 2 unrelated subarrays specified by an array reference and start and end indices.

Improve this answer

2 Comments

I don't think K is an input, but you need to look at all possible values of K, i.e. all possible partitions. For each K, you find the max values of left and right subarrays, and find their absolute difference. Then, you should find the partition where the absolute difference is maximal.
Unfortunately, this question means exactly what it means. Finding the maximum absolute difference between two elements of the 2 arrays is not a big deal. @devjuth is right with his comment. K is not an input it just indicates what 2 subarrays look like.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.