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

Sort by

recency

|

1260 Discussions

|

  • 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;
    }

  • afzal_saiyed931
     + 0 comments
    def pairs(k, arr):
    # Write your code here
    
    temp = set(arr)
    count = 0
    for i in range(len(arr)):
        diff = arr[i] - k
        if diff in temp:
            count += 1
    return count

  • spriyamalar
     + 0 comments
    public static int pairs(int k, List<Integer> a) {
    List<Integer> arr = new ArrayList<>(a);
    Collections.sort(arr);
    int leftptr = 0;
    int rightptr = 1;
    int pairs = 0;
    while(rightptr>leftptr && rightptr<arr.size()) {
        int diff = arr.get(rightptr)-arr.get(leftptr);
        if(diff == k) {
            pairs++;
            rightptr++;
        } else if(diff > k) {
            if(rightptr-leftptr > 1) leftptr++;
            else if(rightptr-leftptr == 1) {
                leftptr++;
                rightptr++;
            }
        } else {
            rightptr++;
        }
    }
    return pairs;
}

  • andrea_laforgia
     + 0 comments

    Kotlin

    fun pairs(k: Int, arr: Array<Int>): Int {
    arr.sort()
    val valueSet = arr.toHashSet()
    var counter = 0

    for (i in arr.size - 1 downTo 0) {
        if ((arr[i] - k) in valueSet) {
            counter++
        }
    }
    
    return counter
}

  • michaelchen0611
     + 0 comments

    Sort the array then use binary search

    1. Time Complexity: O(nlog(n))
    2. Space Complexity: O(1)
    bool binary_search(int* arr, int target, int l, int r){
    while(l <= r){
        int mid = l + (r-l)/2;
        if (arr[mid] == target){
            return true;
        }
        else if (arr[mid] > target){
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }
    return false;
}

void swap(int* a, int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int* arr, int l, int r){
    int pivot = arr[r];
    int start_idx = l;
    int bigger_idx = l;
    for (int i = start_idx; i<r; i++){
        if (arr[i] < pivot){
            swap(&arr[i], &arr[bigger_idx]);
            bigger_idx ++;
        }
    }
    swap(&arr[r], &arr[bigger_idx]);
    return bigger_idx;
}

int* my_q_sort(int* arr, int l, int r){
    if (l < r){
        int idx = partition(arr, l, r);
        my_q_sort(arr, l, idx-1);
        my_q_sort(arr, idx+1, r);
    }
    return arr;
}

int pairs(int k, int arr_count, int* arr) {
    int res_count = 0;
    arr = my_q_sort(arr, 0, arr_count-1);
    for (int i = 0; i<arr_count-1; i++){
        bool find_pair = binary_search(arr, arr[i]+k, 0, arr_count-1);
        if (find_pair == true){
            res_count ++;
        } 
    }
    return res_count;
}