This post is inspired by How to solve the Sherlock and Anagrams coding challenge in JavaScript by Mihail Gaberov. I would like to share my experience about how to construct my thoughts, and optimized my code to pass the time constraints. This coding challenge is called “Count Triplets.”
Problem
You are given an array and you need to find number of tripets of indices (i, j, k) **such that the elements at those indices are in geometric progression for a given common ratio **r and i < j < k.
For example, arr = [1,4,16, 64]. If r = 4, we have_ [1, 4, 16] **and **[4, 16, 64]** at indices **(0, 1, 2)** and **(1, 2, 3)_.
Input Parameters
- arr : an array of integers
- r: an integer, the common ratio
Constrains
- 1 ≤ n ≤ 105 n is the size of arr
- 1 ≤ r ≤ 109 r is the ratio
- 1 ≤ arr[i] ≤ 109 the each number inside array is between 1 to 109
Output Format
Return the count of triplets that form a geometric progression.
Analyze
In order for myself to have a better understanding, I need to have the following information:
- What is geometric progression
- Is the array sorted or not
What I know from the description of problem, and the constraints:
- From the constraints, the performance of your algorithm needs to put into consideration. O(n3) won’t pass the testing.
- From the output, we do not need to list all the combinations that result from the program, we only need to have a count of all the combination. So original index of each element does not need to be kept. So we can sort the array if that is needed.
Geometric Progression
“In mathematics, a geometric progression, also known as a geometric sequence, is a sequence of numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio. For example, the sequence 2, 6, 18, 54, … is a geometric progression with common ratio 3. Similarly 10, 5, 2.5, 1.25, … is a geometric sequence with common ratio 1/2.
Examples of a geometric sequence are powers rk of a fixed number r, such as 2k and 3k. The general form of a geometric sequence is
ar, ar2, ar3,* ar4*…..
where r ≠ 0 is the common ratio and a is a scale factor, equal to the sequence’s start value.”
How does it work in our problem?
From the example:
arr = [1, 3, 9, 9, 27, 81], r = 3 (this is “common ratio” that indicates in the quote above)
We start from the first element: 1, in order to form a geometric sequence with 3 elements, we need to do
1st element of the geometric sequence is 1
2nd element of the geometric sequence is 1 * r = 1 * 3 = 3
3rd element of the geometric sequence is 2nd element * r = 1rr = 133 = 1 * 32 (this is ar2 in ar, ar2, ar3,* ar4*….. ) .
The first geometric sequence is [1, 3, 9], this combination can be formed by indices [0, 1, 2] and [0, 1, 3].
And we need to go through each element until the element at the last 3th one.
Is the arr sorted or not ?
In the description of Problem, it does not mentioned, so we can assume that the arr is not sorted. Also we can not sort the arr due to the requirement _i < j < k. _If we sort the arr, then _i < j < k _ can not be a guarantee.
Solution
- Build a hashMap. Key is the element in the array, and value is an array to keep the index of this number shown in the array. Go through each element in this array, and store the index of this element in the right place in hashMap.
- A for loop to go through each key in the hashMap
a. The current element is the first number in the geometric sequence.
b. The 2nd number in the geometric sequence is current element * ratio.
c. The 3rd number in the geometric sequence is the 2nd number in the geometric * ratio.
d. Locate these 3 numbers in the hashMap, and get the index array of each number.
e. Use these 3 arrays to calculate the total of geometric sequences. - Return the total amount after loop through all the elements.
Build HashMap
This is a helper function to have the same number is located in the position in the hashMap as a key, and the index indicates this number will be kept in the index of array of the number.
let hashMap = {};
for (let i = 0; i < arr.length; i ++){
let num = arr[i];
if (hashMap[num]){
hashMap[num].push(i);
} else {
hashMap[num] = [];
hashMap[num].push(i);
}
}
return hashMap;
Go through each element of the array, and put each element in the hashMap, it is O(N).
Look up / retrieve a particular element in hashMap is it O(1).
A for loop to go through each key in the hashMap
let count = 0;
for (const numKey in numIndices) {
let num1 = parseInt(numKey);
let num2 = num1 * r;
let num3 = num2 * r;
let num1Arr = numIndices[num1];
let num2Arr = numIndices[num2];
let num3Arr = numIndices[num3];
if (num2Arr && num3Arr) {
for (let i = 0; i < num1Arr.length; i ++){
if (num1Arr[i] < num2Arr[num2Arr.length - 1]){
for (let j = 0; j < num2Arr.length; j++) {
if (num2Arr[j] < num3Arr[num3Arr.length - 1]){
if (num2Arr[j] > num1Arr[i]){
let index = -1;
for (let k = 0; k < num3Arr.length; k++){
if (num3Arr[k] > num2Arr[j]) {
index = k;
break;
}
}
if (index > -1) {
count += num3Arr.slice(index).length;
}
}
}
}
}
}
}
}
Note: numIndices is the hashMap that we built before.
When I run my code against the test cases, there are 3 out of 12 are failed. The failure is due to time out. So I know that the algorithm is OK, but not efficient enough.
Even we use hashMap, but we still need to go through 3 layer of loops, which is O(N3), this algorithm is not optimized. So Google search is a good friend, you can find all kinds of information from it.
Please refer APPROACHES TO THE HACKERRANK COUNT TRIPLETS PROBLEM. it has a solution of O(N).
Conclusion
There is alsways better solution than what you expected. However, each coding challenge is not only practice the skill of using this languase, it also help you to analyze the problem in logic way, and based on the information you can get from the description, input paraments, output requirements, and constrains you can figure out what assumptions that you can make, and what needs to watch out while yo plot your algorithm. Even though I did not pass all the test cases, it could mean I need to use more efficient way to solve problem, or it could be there were corner cases that I did not put into consideration. And refer to other developers’ code or blog, it is still a good way to teach yourself can think different approach. Do not be afraid of failure, you can learn from the failure, and make that experience for advancing yourself.