Create a method that takes in a sorted array of integers and returns a sorted array of the same integers.

Aliviya

I was recently asked to complete a Java method task with only one pass over the input array. After stating that I believed it was not possible to complete the task in one pass, the interviewer ended the interview without giving me the answer. I have gone through this resource but couldn't understand it.

public class SortedArrayOps {  
    public SortedArrayOps() {  

    }  

//    Print at the system out the first two ints found in the sorted array: sortedInts[] whose sum is equal to Sum in a single pass over the array sortedInts[] with no 0 value allowed.  
//  i.e. sortedInts[i] + sortedInts[?] = Sum where ? is the target index to be found to complete the task.  
static void PrintIntSumValues(int Sum, int sortedInts[]) {  
//        need to test to see if the Sum value is contained in the array sortedInts. And, if not do nothing.  
    for(int i=0; i<sortedInts.length; i++) {  
//            ... do some work: algebra and logic ...  
//            System.out.println sortedInts[i]+sortedInts[?] sums to Sum.  
    }  
}  

public static void main(String[] args) {  
    final int[] sortedArray = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
    PrintIntSumValues(48, sortedArray);  
}

jsulm

@Aliviya "Create a method that takes in a sorted array of integers and returns a sorted array of the same integers" - can you please explain better? It is not clear what the task actually was.
Do you mean you need to search for an integer in a sorted array? If so then search for "binary search", is easy to implement.

SimonSchroeder

With the source code you are giving it is something entirely different than the title of your post.

Sure, the obvious way to find the pair of integers would be to have to nested for loops like this:

for(int i = 0; i < sortedInts.length; i++) {
    for(int j = i+1; j < sortedInts.length; j++) {
        // compare and print
    }
}

This is certainly two passes over the array (though technically not two full passes).

The only way I see to not count it as two passes is to use a binary search instead of the inner loop to speed things up. You know which element to look for because you know sortedInts[i] and Sum.

SimonSchroeder

One more thought: The outer loop just needs to run while sortedInts[i] <= Sum/2. Because the numbers are sorted after this point you will not find any hits. Even though this does not reduce complexity, it has a real world impact on runtime (if no match is found).

JonB

@SimonSchroeder , @Aliviya
Now that I understand what the question/goal actually is...! :)

First, your last can be improved a little bit. In addition to your stopping outer loop when it reaches Sum / 2, you can stop inner loop when sortedInts[i] + sortedInts[j] > Sum, you don't need the j loop to carry on up to sortedInts.length.

But secondly, the present way is somewhere around O(n^2) (even if it's like O(n^2) / 2 if you know what I mean). It still involves come complete/partial j loop inside the i loop. ISTM the trick is not to have an inner j loop but rather: set j, as a variable outside the i loop, initially to sortedInts.length - 1. Now as you loop through i incrementing look at sortedInts[i] + sortedInts[j] < Sum (note that is < less than). Once that is true you decrement the j variable till sortedInts[i] + sortedInts[j] > Sum, only then do you do next incremented i iteration (while retaining where j got to). Basically you only do "one pass" through the array, but with i as the lower bound and j as the upper bound moving towards each other till they meet.

So something along the lines of:

int i = 0, j = sortedInts.length - 1;
while (i < j)
{
    int sum = sortedInts[i] + sortedInts[j];
    if (sum == Sum)
        return (i, j);
    else if (sum < Sum)
        i++;
    else if (sum > Sum)
        j--;
    else
        throw "Algorithm logic does not work! :(";
}
return ();

@SimonSchroeder (a) is this algorithm right and (b) isn't this O(n)? :)

SimonSchroeder

@JonB said in Create a method that takes in a sorted array of integers and returns a sorted array of the same integers.:

you can stop inner loop when sortedInts[i] + sortedInts[j] > Sum, you don't need the j loop to carry on up to sortedInts.length.

You are right about that. However, the two nested loops are only the trivial way to do it (and not the correct solution, like you said it is O(n^2)). My suggested way is to use binary search instead of the inner loop and gave some hints what is necessary for this to work (didn't want to give away the whole solution). This approach would then yield O(n*log(n)) instead. Usually, this is considered good complexity. The question might hint at recursion (which in my opinion would be the easiest solution for binary search).

@JonB said in Create a method that takes in a sorted array of integers and returns a sorted array of the same integers.:

(a) is this algorithm right and (b) isn't this O(n)? :)

(a) I am trying hard to find overlooked corner cases where your algorithm might fail. I am 99% certain there aren't any. One small thing though: It is not explicitly stated, but I read the assignment that additionally i!=j. This would be an easy adjustment of your algorithm before you return (i,j).
(b) It is O(n). I just don't think that they would expect you to come up with this solution on the spot in a job interview ;)

JonB

@SimonSchroeder said in Create a method that takes in a sorted array of integers and returns a sorted array of the same integers.:

I just don't think that they would expect you to come up with this solution on the spot in a job interview ;)

I suggest this would be exactly what they wanted the interviewee to come up with! It shows a different way of thinking about it from the standard for loops approach. Heck, my first interview I was supposed to come with The Sieve of Eratosthenes!

One small thing though: It is not explicitly stated, but I read the assignment that additionally i!=j. This would be an easy adjustment of your algorithm before you return (i,j).

? Don't follow. My loop only runs while (i < j). If it reaches i==j it would never return (i, j) but will always exit the loop and return (), for "not found".

SimonSchroeder

@JonB said in Create a method that takes in a sorted array of integers and returns a sorted array of the same integers.:

My loop only runs while (i < j).

I was too concentrated on the loop body, so I overlooked that. You are right!