5
\$\begingroup\$

Below is the program to find k-complementary pairs: K = A[i] + A[j];.

package org.test;

import java.util.HashMap;
import java.util.Map;

public class ComplementaryPairs {

    public int noOfComplementaryPairs(int arr[],int k){
        int result = 0;
        for(int i=0;i<=arr.length;i++){
            for(int j=i;j<arr.length-1;j++){
                if(arr[i] + arr[j+1] == k){
                    result++;
                }
            }
        }
        return result * 2;
    }
    public static void main(String[] args) {
        int[] intArray = new int[] {4,5,6,3,1,8,-7,-6};
        int k = 1;
        System.out.println("No of k complementary pairs : "+new ComplementaryPairs().noOfComplementaryPairs(intArray, k));
    }

}

What is the time complexity of the above program? Is there a better way to optimize it further?

\$\endgroup\$
  • 2
    \$\begingroup\$ Why did you create a HashMap to store a single integer value? Did the problem specify that you needed to use a HashMap? \$\endgroup\$ – JS1 Oct 24 '16 at 7:17
  • \$\begingroup\$ No there is no such requirement that's silly of me I wanted to use hashmap with some different idea in my mind but did not remove it once done with program knowing its of no use. I have edited the above program with by changing it from hashmap to int. \$\endgroup\$ – SiddP Oct 24 '16 at 7:34
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Vogel612 Oct 25 '16 at 11:54
10
\$\begingroup\$

Current algorithm

The time complexity of the current solution is O(N²): for a given array of length N, it needs to loop through its elements from 0 to its length, and then for each of those, loop again through the elements after it. Note that it is still O(N²), even with the logic of avoiding duplicate indexes (if the pair (0,1) was a solution, it always follows that (1,0) is one, so we don't need to test it).

About the code itself, the first for loop is deceiving:

for(int i=0;i<=arr.length;i++){
    for(int j=i;j<arr.length-1;j++){
        if(arr[i] + arr[j+1] == k){

It makes the reader think that i will go up to arr.length. What's worse, it makes the reader think the algorithm fails because we fetch arr[i] later on, which cannot work for arr.length (and would fail with an ArrayIndexOutOfBoundsException). In reality, it won't, because there is a second inner loop of j going from i to arr.length-1, so when i is greater than arr.length-1, nothing will happen anyway.

I suggest making that clear in the bounds used. Consider having:

for(int i=0;i<arr.length-1;i++){
    for(int j=i;j<arr.length-1;j++){
        if(arr[i] + arr[j+1] == k){

In the same way, instead of reasoning with j+1, you could have j loop through its natural bounds and reason with j:

for (int i = 0; i < arr.length - 1; i++) {
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] + arr[j] == k) {

With those bounds, it's clear to everyone reading the code that no out of bounds exception can happen. Note also how I added white spaces around the different operators and calculations: it adds to clarity.

Also, maybe I wouldn't make this method an instance method, rather a static one that is directly invoked in main.

Better performance

It would be possible to solve this problem in O(N) time complexity, instead of O(N²), at the expense of also being O(N) in terms of memory.

The idea is that we want to avoid looping through the array again and again. Here's another approach:

  • Go through the array once, and store in a Map the difference of the wanted sum and the current element mapped to how many times it occured. Effectively, this map remembers how much we're missing for an element at a given index so that the sum can be reached.
  • Go through the array a second time, and check whether the map contains this element. If it does, then it means that our map contains an element e for which e = sum - arr[i], so it means that we've found a matching pair. And the number of matching pair we found, is the number of times this element appears in the array, which is the value of the map.

That's how it would look like with the example in the question where the sum to look for is 1:

          arr =  4   5   6   3   1   8  -7  -6
1st pass, map = -3  -4  -5  -2   0  -7   8   7  <-- how much we need to add to find the sum
    2nd pass  =  x   x   x   x   x   o   o   x  <-- the initial array only contains the element marked o

This shows that there are 2 such pairs, and that is the answer. As an example of putting this into code, and using Java 8, you could have:

public int noOfComplementaryPairs(int arr[], int k) {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < arr.length; i++) {
        map.merge(k - arr[i], 1, Integer::sum);
    }
    return Arrays.stream(arr).map(element -> map.getOrDefault(element, 0)).sum();
}
\$\endgroup\$
2
\$\begingroup\$

The solution that @Tunaki suggested works, but doesn't count duplicates. For example, in the input array: [1, 8, -3, 0, 1, 3, -2, 4, 5] and k=6, @Tunaki's answer will output 6 (instead of 7), because the number 3 is twice in the array.

Consider this implementation which handles duplicates correctly, using python:

from collections import Counter

def solution(k, nums):
    # a list of opposite to the numbers in the input list.
    # for example, if 4 is in the input list and 6 is k,
    # then 6-4=2 will be added to the diffs list
    diffs = []
    for num in nums:
        diffs.append(k-num)

    k_complementary_sum = 0

    nums_counter = Counter(nums)  # counting how many times a number appears in the input list
    for num in diffs:
        k_complementary_sum += nums_counter[num]  # if the diff is not in the original input, the Counter will give 0
    return k_complementary_sum

I'm using Counter to sum up the number that element is in the input list.

Check this out also: https://stackoverflow.com/a/36384804/8953378 I'm not sure about the complexity of this answer, but is a two liner and it does the job :)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.