Beautiful Triplets

It seems that today is going to be another nice day in the Twin Cities of Minneapolis and St. Paul. For some reason I woke up a few minutes shorter than 04:00 AM. I decided to give a try to the HackerRank challenge that I received via email.

If interested take a look at the requirements on how to determine what makes a triplet beautiful.

Following is console output of my solution using Java 8 on the Eclipse IDE.

5 1
2 2 3 4 5

(2, 3, 4)
(2, 3, 4)
(3, 4, 5)
3


7 3
1 2 4 5 7 8 10

(1, 4, 7)
(2, 5, 8)
(4, 7, 10)
3

10 3
1 6 7 7 8 10 12 13 14 19

(7, 10, 13)
(7, 10, 13)
2

Please note that one is only supposed to return the count of triplets and not generate any other output. I displayed the triplets in the console for testing purpose only.

While I was working in the solution I put together some code using a brute force approach. The code follows:

    // **** brute force approach (too slow) ****
    static int theTriplets(int d, int[] arr) {
    	
    	int count = 0;
    	
    	for (int i = 0; i < arr.length - 2; i++) {
    		
    		for (int j = i + 1; j < arr.length - 1; j++) {
    			
    			for (int k = j + 1; k < arr.length; k++) {
    				
    				if ((arr[j] - arr[i] == d) && (arr[k] - arr[j] == d)) {
    					
    					// ???? ????
    					System.out.println("(" + arr[i] + ", " + arr[j] + ", " + arr[k] + ")");

    					count++;
    				}
    				
    			}
    		}
    	}
    	
    	return count;
    }

The requirements call for i < j < k and there are 3 values in a triplet so we let’s try 3 loops. The requirements call for arr[j] – arr[i] == d and arr[k] – arr[j] == d. The brute force approach produces the expected results in the test cases, but as expected it is O(n^3). It was not going to pass the test cases.

	// Complete the beautifulTriplets function below.
    static int beautifulTriplets(int d, int[] arr) {

    	// **** ****
    	int count = 0;
    	
     	for (int i = 0; i < arr.length - 2; i++) {
    		
    		for (int j = i + 1; j < arr.length - 1; j++) {
    			    			
    			// **** arr[j] - arr[i] == d ****
    			if (arr[j] - arr[i] == d) {
    				
        			for (int k = j + 1; k < arr.length; k++) {
        				        				
        				// **** arr[k] - arr[j] == d ****
        				if (arr[k] - arr[j] == d) {
        					
        					// ???? ????
        					System.out.println("(" + arr[i] + ", " + arr[j] + ", " + arr[k] + ")");
        					
        					count++;
        					break;
        				}
        				
        			}
     
    			}

    		}
    		
    	}
    	
    	// **** ****
    	return count;
    }

By exiting the first two loops when the condition will not be met and by exiting the third one when the condition has been met, the code passed all ten tests.

The complete code for my solution can be found in my GitHub repository.

If you are interested in learning make sure you read and experiment. That is the best way to learn!

If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.

Keep on reading and experimenting. It is the best way to learn!

John

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.