Question

Write a method, twoSumSorted2, that solves the following variant of the Two-Sum problem:

Given a sorted array of integers where each element is unique and a target integer, return in an Array List, the indices of all pairs of elements that sum up to the target. Each pair of indices is also represented as an Array List (of two elements). Therefore, the method returns an Array List of an Array List of size 2. If no pair in the input array sums up to the target, then the method should return an empty list.

public class Hw2_p1 {
  
   // HW2 Problem 1 Graded Method
   public static ArrayList<ArrayList<Integer>> twoSumSorted(int[] A, int target) {
       ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
      
       // Your code starts
      
      
       // Your code ends
      
       return ans;
   }

  
   // Test driver for twoSumSorted2
   public static void main(String[] args) {
      
   }

}

The following are two sample runs:

Input:   ? = [−7, −5, −2, 0, 1, 6, 7, 8, 9],   ?????? = 1

Return value:   [0,7], [1, 5], [3, 4]

Explanation: The pairs in the input array that sum up to 1 are [−7, 8], [−5, 6] and [0, 1]. Their indices are [0, 7], [1, 5] and [3, 4] respectively.

Input:   ? = [−2, 0, 1, 6, 7, 8],   ?????? = 3

Return value:   [ ]

Explanation: No pair of elements in input array sums up to 3. The returned list is thus empty.

Your method must have time complexity ?(?), where ? is the length of the input array.

Answer 1

The code is

import java.util.*;
public class Hw2_p1 {
  
// HW2 Problem 1 Graded Method
public static ArrayList<ArrayList<Integer>> twoSumSorted(int[] A, int target) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
  
// Your code starts
int l=0,r=A.length-1;
while(l<r){
if(A[l]+A[r]==target){
// System.out.println("Here");
ArrayList<Integer> temp=new ArrayList<Integer>();
temp.add(l);
temp.add(r);
ans.add(temp);
l++;
}
else if(A[l]+A[r]<target){
l++;
}
else r--;
}
  
// Your code ends
  
return ans;
}

  
// Test driver for twoSumSorted2
public static void main(String[] args) {
int[] A={-7,-5,-2,0,1,6,7,8,9};
System.out.println(twoSumSorted(A,1));
int[] B={-2,0,1,6,7,8};
System.out.println(twoSumSorted(B,3));
}

}

The output is