CODEWITHSUNDEEP
javaarrays
Pernicious Rage
Pernicious Rage

Reputation: 35

How to check if an array has two different pairs of matching values?

public static boolean hasTwoPair(int[] arrayOfInts){    
}

The method is supposed to return true if it can find two different pairs of matching int values. So if the array was {2,2,4,7,7}, it should return true because it has two 2s and two 7s.

It only applies to different pair values though. If it was {2,2,2,2,5}, it would return false because they are not different pair values.

EDIT: This is what I have so far for the body of the method:

     boolean pairFound = false;
    int pairValue;

    for(int s = 0; s < arrayOfInts.length - 1; s++){
        pairValue = arrayOfInts[s];

        for(int c = s + 1; c < arrayOfInts.length; c++){
            if(pairValue == arrayOfInts[c])
                pairFound = true;
        }
    }

    return false; //placeholder

I'm not sure where to go from here.

Upvotes: 0

Views: 5643

Answers (4)

David Ongaro
David Ongaro

Reputation: 3946

You don't need to sort the array, that would give O(n*log(n)) complexity. But your current solution is even worse since it's yielding O(n^2) complexity. But you also don't need a HashMap. A Set and an integer is enough:

  • For each array element do
    • Check: is the element already in the set?
      • If not put it into the set
      • If yes check if it's equal to your last found Int pair (yes, use a boxed Int, not a primitive int here, to be able to initialize it with null)
        • If it's equal continue
        • If it's not equal
          • If the last found pair is null set it to elements value
          • Otherwise you're done and you have at least 2 different pairs
  • If you iterated over the list without reaching the last condition you don't have 2 different pairs

As for the Set implementation I would recommend a HashSet

There is more to say here though. If you implement it like this you make no assumption about integers and indexable arrays. All you need is a list of comparable elements. So you could make the signature of your method much more generic:

public static boolean hasTwoPair(Iterable<E> iterable)

But since arrays don't support generics and the Iterable interface every client of this method would have to transform Array parameters to an Iterable with the asList() method. If that's too inconvenient you can provide another method:

public static <T> boolean hasTwoPair(T[] array)

In general it's a good idea to use the most generic type possible when you design API's (also see Item 40 and 52 in "Effective Java, Second Edition")

Upvotes: 0

nhgrif
nhgrif

Reputation: 62072

Since you haven't actually tried any code, I'll give a description of how to solve this problem, but no actual code.

Start with a boolean like pairFound that's initialized to false and change to true when you find your first pair. Additionally, you'll need an int (pairValue to keep track of the value of the first pair found (if you found one).

Iterate through, looking for a pair. If you find a pair, and pairFound is false, set pairFound to true, and set pairValue to the value of your first found pair. Now keep iterating through.

If you find a pair and pairFound is true and the pair is != pairValue, then return true;. If you iterate through everything and haven't returned true yet, then you can return false.

Based on your updated question, you're pretty close.

boolean pairFound = false;
int pairValue = Integer.MIN_VALUE;  
//or some value that arrayOfInts will never have based on context

for(int s = 0; s < arrayOfInts.length - 1; s++){
    if(arrayOfInts[s] == pairValue) { 
        continue; 
    }
    for(int c = s + 1; c < arrayOfInts.length; c++){
        if(arrayOfInts[s] == arrayOfInts[c]) {
            if(arrayOfInts[s] != pairValue) {
                if(pairFound) {    
                    return true;
                }
                pairValue = arrayOfInts[s];
                pairFound = true;
                break;
            }
        }
    }
}
return false;

Upvotes: 2

Ted Hopp
Ted Hopp

Reputation: 234857

Sort the array. Then look for the first two consecutive values that match. If found, skip to the first entry that is different from the matched pair and repeat. If you reach the end of the array before either the first or second search succeeds, return false.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727077

This task asks you to build a list of counts:

  • Create a data structure (say, a Map<Integer,Integer>) containing a count for each number from the array.
  • Go through the map, and count the number of entries with the count of two and above.
  • If you counted two or more items, return true; otherwise, return false.

The counts for your first example would look like this:

V   #
-   -
2 - 2
4 - 1
7 - 2

You have two items (2 and 7) with counts of 2, so return true.

The counts for your second example look like this:

V   #
-   -
2 - 4
5 - 1

There is only one item with the count above 2, so return false.

If you use a HashMap, this algorithm produces an answer in O(n).

Upvotes: 2

Related Questions