DEV Community

Simon Green
Simon Green

Posted on


It's all good

Weekly Challenge 199

Challenge, My solution

Task 1: Good Pairs


You are given a list of integers, @list.

Write a script to find the total count of Good Pairs. A pair (i, j) is called good if list[i] == list[j] and i < j.

My solution

One of the challenges when completing these tasks is needless optimizations. Given that the input list is relatively small there is a fine line between being clever and just brute forcing the solution.

The brute force solution is (where n is the length of the array) to go through all combinations of i and j (where i is an iterator from 0 to n - 2 and j is an iterator from i + 1 to n - 1), and count the occurrences where the value in that position is the same. And that's a perfectly acceptable solution in solving the task. I'd approve that pull request every day of the week :)

The solution I took is a little more complex, but will work on extremely large lists better. The first thing I do is count the frequency of each 'integer'. I put that in quotes as in Python they really are strings. This is stored as the freq dict (hash in Perl).

I then loop through the frequency counts (the values of the freq dict). If the frequency is greater than one, we have good pairs. The number pairs is the sum of 1 + ... + n-1. Rather than calculating the sum by hand, we know that the sum of n can be expressed a n ร— (n + 1) รท 2, which is the formula that I use.


$ ./ 1 2 3 1 1 3

$ ./ 1 2 3

$ ./ 1 1 1 1
Enter fullscreen mode Exit fullscreen mode

Task 2: Good Triplets


You are given an array of integers, @array and three integers $x, $y, $z.

Write a script to find out total Good Triplets in the given array.

A triplet array[i], array[j], array[k] is good if it satisfies the following conditions:

1) 0 <= i < j < k <= n (size of given array)
1) abs(array[i] - array[j]) <= x
1) abs(array[j] - array[k]) <= y
1) abs(array[i] - array[k]) <= z

My solution

My first observation is that k can be the size of the array. This will cause an out of bounds errors. For example, if an array has three elements, array[3] is not valid. So I'm assuming that for the first condition it is meant that k < n.

My next observation is that this very similar to the first task in week 196, so most of the code comes from that solution.

The first thing I do is remove the last three values from the input to represent x, y and z.

For this task I used the combinations method from itertools (Python) or Algorithm::Combinatorics (Perl) to generate all combinations of positions (not values) from 0 to one less than the length of the array.

For each iteration, I (numerically) sort the numbers to ensure i < j < k. I then check if the other three criteria are met. If it is, I add one to count.


$ ./ 3 0 1 1 9 7 7 2 3

$ ./ 1 1 2 2 3 0 0 1
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

50 CLI Tools You Can't Live Without

The top 50 must-have CLI tools, including some scripts to help you automate the installation and updating of these tools on various systems/distros.