We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. Pairs
  5. Discussions

Pairs

  • rajivaiyer
     + 0 comments

    My Java 8 solution, which passes all test cases, for a Max Score of 50:

    (1) Sort the Array in Ascending Order.

    (2) Iterate through the array sequentially from arrIndex = 0 all the way to arrIndex = arr.size() - 2, and do the following:

    (2) (a) Make a subList which spans from arrIndex + 1 to the last index of the array. This is our way of narrowing our search space. We expect the other value in the pair to occur in this space.

    (2) (b) For the element at arr[arrIndex] : do a "Binary Search" through the Narrowed Sorted Sublist (costing O(log (n)) - to attempt to find the "other corresponding expected value", which would result in the "target difference". If search is successful, then Another Pair has been FOUND. At this point, we also increment the subListStartIndex, narrowing our search space further.

    Overall Expected Worst Case Time Complexity: O(n * log(n)).

        public static int pairs(int k, List<Integer> arr) {
        // Write your code here
        int numPairs = 0;

        Collections.sort(arr);
        
        for (int arrIdx = 0, subLstStrtIdx = (arrIdx + 1) ; 
             arrIdx < (arr.size() - 1) && subLstStrtIdx <= (arr.size() - 1) ; 
             arrIdx++) {

            int curElemVal = arr.get(arrIdx);
            int otherExpElemVal = (curElemVal + k);
            
            List<Integer> curSubLst = getSubList(arr, subLstStrtIdx, arr.size());

            int otherExpElemIdx = 
                Collections.binarySearch(curSubLst, otherExpElemVal);
                
            if (otherExpElemIdx >= 0) {

                // Other Expected Element found - arrIdx.e. Another Pair Found.
                numPairs++;
                // We can narrow the Search-Space further.
                subLstStrtIdx += (otherExpElemIdx + 1);

            }
        }
        
        return numPairs;
    }