Hackerrank Sales by Match problem - I'm getting answer but can't return it (my1st recursion attempt)

[Chaz Winter]

I'm trying to complete the Hackerrank Sales by Match problem:
www [dot] hackerrank [dot] com/challenges/sock-merchant/problem?isFullScreen=true

My method is meant to just look for duplicates, remove them, then call itself to look for another duplicate. If there are no duplicates, then it just returns the number of times it found a duplicate.

I added a bunch of sysout lines to help debug, and according to the debug output, I am successfully getting the count variable to correctly identify the number of duplicates. Here are my problems:

1. Why do I need the return statement at the end? And how is my code even reaching it? When the if statement is true, it reaches a return statement. When the if statement is false, the method just calls itself again. So that last return statement at the end should never be reached, but somehow it is being reached and returning a 1.
2. See my debug output below the code. Why is my for loop continuing to run even after the if statement is true (and therefore my method reaches a return statement and should stop)?
-----if it makes a difference, when I run it against the other test case, the method actually stops when there are no more duplicates, but still returns a 1 instead of the actual count (as if it's reaching the return statement at the end of the code somehow).

class Result {

    /*
     * Complete the 'sockMerchant' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. INTEGER_ARRAY ar
     */

    public static int sockMerchant(int n, List<Integer> ar) {
        return matchCheck(ar, 0);
    }
    
    public static int matchCheck(List<Integer> ar, int newCount){
        ar.sort(Comparator.naturalOrder());
        System.out.println("matchCheck method has been called!");
        TreeSet set = new TreeSet<Integer>(ar);
        System.out.printf("TreeSet is length %d: ", set.size());
        System.out.println(set);
        System.out.printf("ArrayList is length %d: ", ar.size());
        System.out.println(ar);
        
        if (set.size() == ar.size()) {
            System.out.println("TreeSet and ArrayList are equal in size");
            System.out.println("We should return " + newCount);
            return newCount;
        }
        else {
            System.out.println("TreeSet and ArrayList are different sizes, so...");
            for (int i = 0; i < ar.size() - 1; i++) {
                for (int j = i + 1; j < ar.size(); j++) {
                    System.out.printf("Checking %d and %d%n", ar.get(i), ar.get(j));
                        if (ar.get(i) == ar.get(j)) {
                            System.out.printf("%d and %d are a match on index %d and %d%n",
                                ar.get(i), ar.get(j), i, j);
                            newCount++;
                            ar.remove(j);
                            ar.remove(i);
                            System.out.println("Count is " + newCount);
                            matchCheck(ar, newCount);   
                        }
                }
            }
        } 
        return newCount;  
    }
}

The debug output is as follows:

matchCheck method has been called!
TreeSet is length 4: [10, 20, 30, 50]
ArrayList is length 9: [10, 10, 10, 10, 20, 20, 20, 30, 50]
TreeSet and ArrayList are different sizes, so...
Checking 10 and 10
10 and 10 are a match on index 0 and 1
Count is 1
matchCheck method has been called!
TreeSet is length 4: [10, 20, 30, 50]
ArrayList is length 7: [10, 10, 20, 20, 20, 30, 50]
TreeSet and ArrayList are different sizes, so...
Checking 10 and 10
10 and 10 are a match on index 0 and 1
Count is 2
matchCheck method has been called!
TreeSet is length 3: [20, 30, 50]
ArrayList is length 5: [20, 20, 20, 30, 50]
TreeSet and ArrayList are different sizes, so...
Checking 20 and 20
20 and 20 are a match on index 0 and 1
Count is 3
matchCheck method has been called!
TreeSet is length 3: [20, 30, 50]
ArrayList is length 3: [20, 30, 50]
TreeSet and ArrayList are equal in size
We should return 3
Checking 20 and 50
Checking 30 and 50
Checking 20 and 50
Checking 30 and 50
Checking 20 and 50
Checking 30 and 50

[Carey Brown]

I don't see why you've turned this into a recursive problem or why you need to remove elements from ar. Once you sort it you can just start at the beginning and if the current value matches the previous value you have a pair, and so on.

[Chaz Winter]

Carey Brown wrote:I don't see why you've turned this into a recursive problem

Because I wanted to

[Carey Brown]

On line 42 you don't do anything with the newCount that is being returned.

[Carey Brown]

The return at line 28 only unwinds the recursive calls one level and you eventually get back to a call you made on line 32, which, after the loops are exhausted will end up at the return at the very end.

[Piet Souris]

You do not need that double for-loop. In matchCheck, the list is sorted, so you can simply do:

public static int getPairs(List<Integer> list) {
    list.sort(Comparator.naturalOrder());
    return helper(list, 0);
}

private static int helper(List<Integer> list, int count) {
    return list.size() == 0 || list.size() == 1 ? count :
           list.get(0) == list.get(1)           ? helper(list.subList(2, list.size()), count + 1) :
                                                  helper(list.subList(1, list.size()), count)
    ;
}

[Chaz Winter]

Carey Brown wrote:On line 42 you don't do anything with the newCount that is being returned.

That's what I thought as well, but if I change that line to

return -1;

-1 is what ends up on stdout. I reach my return statement on line 28 (debug prints the line right before it), and then the for loop runs again for some reason after the return, and the return on 42 is what gets passed.

[Chaz Winter]

Carey Brown wrote:The return at line 28 only unwinds the recursive calls one level and you eventually get back to a call you made on line 32, which, after the loops are exhausted will end up at the return at the very end.

Okay, so if I'm understanding you correctly, if I make a recursive call, the return statement doesn't get returned to the method that originally called it, but rather gets returned to the previous method call (ie the one that called itself)? So after my matchCheck method calls itself three times, it finally returns an int, but instead of returning it to the original sockMerchant method that called matchCheck, the int gets returned to the 3rd matchCheck that was called?

And so what happens is the very first matchCheck call, which incremented newCount by 1, is the one that actually returns the int, which is why my code gets 1 on stdout instead of 3. Correct?

This is why I wanted to use recursion - I can't learn the details of recursion without trying to use it on something.

[Carey Brown]

I think you've got the gist of it now.

You can try

newCount = matchCheck(ar, newCount); 

[Chaz Winter]

Carey Brown wrote:I think you've got the gist of it now.

You can try

newCount = matchCheck(ar, newCount); 

As a test, I placed that line directly above the return statement at the very end of the code, and sure enough, I can now see (via the debug output) the newCount go from 3, stay 3, then go to 2, and then 1, as the methods "unwind."

I'm not entirely sure how I could use the existing recursion to actually solve the problem, but I'm glad to actually learn something new in the process.

Count is 4
matchCheck method has been called!
TreeSet is length 2: [2, 3]
ArrayList is length 2: [2, 3]
TreeSet and ArrayList are equal in size
We should return 4
matchCheck method has been called!
TreeSet is length 2: [2, 3]
ArrayList is length 2: [2, 3]
TreeSet and ArrayList are equal in size
We should return 4
matchCheck method has been called!
TreeSet is length 2: [2, 3]
ArrayList is length 2: [2, 3]
TreeSet and ArrayList are equal in size
We should return 3
matchCheck method has been called!
TreeSet is length 2: [2, 3]
ArrayList is length 2: [2, 3]
TreeSet and ArrayList are equal in size
We should return 2
matchCheck method has been called!
TreeSet is length 2: [2, 3]
ArrayList is length 2: [2, 3]
TreeSet and ArrayList are equal in size
We should return 1

EDIT: Sorry, that's the output from the other test case...which now that I'm looking at it, it actually doesn't keep testing values like the first test case. It actually hits "true" every time, unlike the first test case, which hits false for some reason before exhausting all checks and using the return statement at the end of the code.

[Chaz Winter]

Thank you for helping me understand recursion. Now that I get it, I decided to avoid it for this particular problem (though it was fun debugging and seeing how it actually works).

I ended up solving it like this:

public static int sockMerchant(int n, List<Integer> ar) {
    int count = 0;
    TreeSet<Integer> set = new TreeSet<Integer>(ar);
    for (int x : set) {
        count += Collections.frequency(ar, x) / 2;     //it's an int, so any 0.5's from an odd number of occurrences won't be added!
    }
    return count;
}

I'm sure more experienced coders could solve it even more simply, but that's what I came up with.

[Carey Brown]

I like your solution. Small and readable.

This is what I came up with which has the advantage of only making two passes through the data, once for sorting, and once for counting.

	public static int sockMerchant( int n, List<Integer> ar )
	{
		ar.sort( Comparator.naturalOrder() );
		int			count = 0;
		for( int i=1 ; i < ar.size() ; i++ )
			if( ar.get( i-1 ) == ar.get( i ) )
			{
				count++;
				i++;
			}
		return count;
	}

[Piet Souris]

Indeed, nice and very readable. Here are two other ways that are O(n):

public static int getPairs1(List<Integer> list) {
    var freqs = new HashMap<Integer, Integer>();
    for (int i: list) freqs.merge(i, 1, Integer::sum);
    return freqs.values().stream().mapToInt(i -> i / 2).sum();
}

public static int getPairs2(List<Integer> list) {
    return list.stream()
        .collect(groupingBy(i -> i, counting()))
        .values().stream()
        .mapToInt(i -> i.intValue() / 2)
        .sum()
    ;
}

[Chaz Winter]

Piet Souris wrote:Indeed, nice and very readable. Here are two other ways that are O(n):

public static int getPairs1(List<Integer> list) {
    var freqs = new HashMap<Integer, Integer>();
    for (int i: list) freqs.merge(i, 1, Integer::sum);
    return freqs.values().stream().mapToInt(i -> i / 2).sum();
}

public static int getPairs2(List<Integer> list) {
    return list.stream()
        .collect(groupingBy(i -> i, counting()))
        .values().stream()
        .mapToInt(i -> i.intValue() / 2)
        .sum()
    ;
}

HashMaps are the other thing I've heard over and over, but never used and don't quite understand. Gonna have to look it up on YouTube and find some problems to solve with it.

[Carey Brown]

A quick benchmark.
Output: seconds for 100,000 iterations
Chaz: 12.606
Carey: 0.173
Piet1: 1.318
Piet2: 1.37

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Random;
import java.util.TreeSet;
import java.util.stream.Collectors;

public class SockCount
{
	static final Random rand = new Random();
	
	public static void main( String[] args )
	{
		rand.setSeed( 424242 );
		long		start, end;
		List<Integer>	ar;
		
		List<Integer>	orig = new ArrayList<>();
		for( int i=0 ; i < 1000 ; i++ )
			orig.add( rand.nextInt(100)+1 );
		
		ar = new ArrayList<>( orig );
		start = System.currentTimeMillis();
		for( int i = 0 ; i < 100_000 ; i++ )
			pairs_Chaz( ar );
		end = System.currentTimeMillis();
		System.out.println( "Chaz: " + ((end-start)/1000.0) );
		
		ar = new ArrayList<>( orig );
		start = System.currentTimeMillis();
		for( int i = 0 ; i < 100_000 ; i++ )
			pairs_Carey( ar );
		end = System.currentTimeMillis();
		System.out.println( "Carey: " + ((end-start)/1000.0) );
		
		ar = new ArrayList<>( orig );
		start = System.currentTimeMillis();
		for( int i = 0 ; i < 100_000 ; i++ )
			pairs_Piet1( ar );
		end = System.currentTimeMillis();
		System.out.println( "Piet1: " + ((end-start)/1000.0) );
		
		ar = new ArrayList<>( orig );
		start = System.currentTimeMillis();
		for( int i = 0 ; i < 100_000 ; i++ )
			pairs_Piet2( ar );
		end = System.currentTimeMillis();
		System.out.println( "Piet2: " + ((end-start)/1000.0) );
	}
	
	public static int pairs_Chaz( List<Integer> ar) {
	    int count = 0;
	    TreeSet<Integer> set = new TreeSet<Integer>(ar);
	    for (int x : set) {
	        count += Collections.frequency(ar, x) / 2;
	    }
	    return count;
	}
	
	public static int pairs_Carey( List<Integer> ar )
	{
		ar.sort( Comparator.naturalOrder() );
		int			count = 0;
		for( int i=1 ; i < ar.size() ; i++ )
			if( ar.get( i-1 ) == ar.get( i ) )
			{
				count++;
				i++;
			}
		return count;
	}
	
	public static int pairs_Piet1(List<Integer> list) {
	    var freqs = new HashMap<Integer, Integer>();
	    for (int i: list) freqs.merge(i, 1, Integer::sum);
	    return freqs.values().stream().mapToInt(i -> i / 2).sum();
	}

	public static int pairs_Piet2(List<Integer> list) {
	    return list.stream()
	        .collect( Collectors.groupingBy(i -> i, Collectors.counting()))
	        .values().stream()
	        .mapToInt(i -> i.intValue() / 2)
	        .sum()
	    ;
	}
}

[Piet Souris]

hi Carey,

yes, I could have expected a performance test!

One remark though: in your Carey-test you create a list ar, that gets sorted. That means that from try 2, the argument-array is already sorted, and that saves a lot of time. I adjusted the test in two ways: one where each list is created in the method itself, and two where I create a general list, and in your method I take a copy and sort that. That gives quite a difference.

But the way to the outcome is much more interesting than the corresponding performance. and OP has quite a few solutions now. Hope he likes it.

[Carey Brown]

Hmmm, I didn't take into account that once the array had be sorted that subsequent calls to sort ran extremely fast. Writing benchmarks is tricky. So here's a more realistic outcome and mine didn't fare so well this time.
Output: seconds per 100,000 iterations
Chaz: 10.5
Carey: 8.358
Piet1: 1.454
Piet2: 1.856

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Random;
import java.util.TreeSet;
import java.util.stream.Collectors;

public class SockCount
{
	static final Random rand = new Random();
	
	public static void main( String[] args )
	{
		rand.setSeed( 424242 );
		long		start, end;
		List<Integer>[]	copies;
		
		List<Integer>	orig = new ArrayList<>();
		for( int i=0 ; i < 1000 ; i++ )
			orig.add( rand.nextInt(100)+1 );
		
		copies = copies( orig, 100_000 );
		start = System.currentTimeMillis();
		for( int i = 0 ; i < 100_000 ; i++ )
			pairs_Chaz( copies[i] );
		end = System.currentTimeMillis();
		System.out.println( "Chaz: " + ((end-start)/1000.0) );
		
		copies = copies( orig, 100_000 );
		start = System.currentTimeMillis();
		for( int i = 0 ; i < 100_000 ; i++ )
			pairs_Carey( copies[i] );
		end = System.currentTimeMillis();
		System.out.println( "Carey: " + ((end-start)/1000.0) );
		
		copies = copies( orig, 100_000 );
		start = System.currentTimeMillis();
		for( int i = 0 ; i < 100_000 ; i++ )
			pairs_Piet1( copies[i] );
		end = System.currentTimeMillis();
		System.out.println( "Piet1: " + ((end-start)/1000.0) );
		
		copies = copies( orig, 100_000 );
		start = System.currentTimeMillis();
		for( int i = 0 ; i < 100_000 ; i++ )
			pairs_Piet2( copies[i] );
		end = System.currentTimeMillis();
		System.out.println( "Piet2: " + ((end-start)/1000.0) );
	}
	
	public static int pairs_Chaz( List<Integer> ar) {
	    int count = 0;
	    TreeSet<Integer> set = new TreeSet<Integer>(ar);
	    for (int x : set) {
	        count += Collections.frequency(ar, x) / 2;
	    }
	    return count;
	}
	
	public static int pairs_Carey( List<Integer> ar )
	{
		ar.sort( Comparator.naturalOrder() );
		int			count = 0;
		for( int i=1 ; i < ar.size() ; i++ )
			if( ar.get( i-1 ) == ar.get( i ) )
			{
				count++;
				i++;
			}
		return count;
	}
	
	public static int pairs_Piet1(List<Integer> ar) {
	    var freqs = new HashMap<Integer, Integer>();
	    for (int i: ar) freqs.merge(i, 1, Integer::sum);
	    return freqs.values().stream().mapToInt(i -> i / 2).sum();
	}

	public static int pairs_Piet2(List<Integer> ar) {
	    return ar.stream()
	        .collect( Collectors.groupingBy(i -> i, Collectors.counting()))
	        .values().stream()
	        .mapToInt(i -> i.intValue() / 2)
	        .sum()
	    ;
	}
	
	static List<Integer>[] copies( List<Integer> list, int n )
	{
		List[] array = new List[ n ];
		for( int i=0 ; i < n ; i++ )
			array[i] = new ArrayList<Integer>( list );
		return array;
	}
}

[Carey Brown]

Interesting observation... On line 4 I replaced "int" with "Integer" so it might not do auto-unboxing and it did shave a few nano-seconds off the time.

	public static int pairs_Piet1( List<Integer> ar )
	{
		var freqs = new HashMap<Integer,Integer>();
		for( Integer i : ar )
			freqs.merge( i, 1, Integer::sum );
		return freqs.values().stream().mapToInt( i -> i / 2 ).sum();
	}

[Piet Souris]

It sure is tricky. When determining the files in the methods themselves, I used for each of the methods

random.ints(size, 0, max).boxed().toList();

but for your method, I also sorted the list with .sorted(), but it differed also between

sorted().boxed().toList()

and

boxed().sorted().toList()