Couple of hints:

• Can be done in O(n) -> single pass through data
• No division necessary and single multiplications by R are all that's needed
• Using map(C++) or dict(Java, Python) is a must -> can be unordered map (saves O(logN))
• Try to think forward when reading a value -> will this value form part of a triplet later?
• No need to consider (R == 1) as a corner case

Very interesting problem and it took a while to think it through properly. If anyone is desperate for the code, drop me a message.

Took me forever to figure this out. It's a really cool problem - the breakthrough came when you realize that, since sequentiality is important, then the array should be walked in reverse because the only values you want to check are those at higher indeces than the one you are checking.

The other big thing to realize is that you're checking for two things, not just one - you're checking for the existence of a value r times the current value, or your checking for a pair that exists for the for the value that begin at r times the current value and also contain r times that value.

For example: Let's say r is 3. If you have a the value you're checking while iterating the array that is also 3, and there's a 9 and a 27 in the dictionary that you've been populating, you should have populated another dictionary and entry for the pair of the values (9, 27) because those are a pair where 27 is r times 9 and if we find a 3 at a lower index, then we know we have a triplet.

So the algorithm is: -- keep two dictionaries: 1. a dictionary to store the number of times each single value that is repeated in the array 2. a dictionary to store any pair of values that are i and (i * r) (using i as the key)

-- Walk the array backwards 1. if the pair dictionary has a value for r times the one you're checking, then you add the number of pairs to the overall count. 2. otherwise, if there's add a new pair and add it to the pair dictionary if there's a value r times the one you're checking in the single value dictionary. 3. otherwise, just add the value to the single value dictionary.

And that will do it.

In Python, O(N) time complexity:

def countTriplets(arr, r):
        count = 0
        dict = {}
        dictPairs = {}

        for i in reversed(arr):
                if i*r in dictPairs:
                        count += dictPairs[i*r]
                if i*r in dict:
                        dictPairs[i] = dictPairs.get(i, 0) + dict[i*r]

                dict[i] = dict.get(i, 0) + 1

        return count

This problem drove me crazy. Finally with the help of editorial and fellow hackerankers I was able to understand the solution. Also I felt this problem is slightly on the difficult side for beginners. The success perecentage of 42% and only around 5.5k submissions justifies it. Don't get disappointed if it doesen't click you. I had spend days trying to get my head over it. Here is the complete logic to help anyone :

Let's take an example to undertsand the core concept behind this problem : {1, 3, 3, 9, 3, 27, 81} . Let common ratio = 3.

1.We will consider every element to be our middle element during our iteration. For any such element a, the number of possible geometric pairs possible are, no. of a/r on the left of a x no. of axr on the right of a.

2.Lets take 9 as our element. 9/3 = 3. 9x3 = 27. The number of 3s present on left of 9 are 2. The number of 27s present on right of 9 is 1. Hence total no. of geometric pairs possible with 9 as the middle element is 2x1 = 2. Do this for all the elements and add them up to get the result.

3.We create an occurence map first and call it rightMap. Now for each element, we first decrement it's count by 1 from the rightMap. Now we check for the number of occurences of axr in the rightMap. ( Let me explain this step with a simple example , say the input is {1,1,1,1 } and ratio = 1, rightMap will be [1->4]. Now we need to check the number of times axr = 1 occurs on the right of a. We do this after decrementing the count of current value by 1 in the rightMap. So rightMap becomes [1->3] . 3 is the number of times aXr occurs on RHS of first 1 )

4.Now we check for a/r counts in left map. We multiply leftCount and rightCount and add them up for each element. The whole idea is that, for each element , leftMap contains the occurence map of the elements on the left of a and rightMap contains the occurence map of the elements on the right of a.

Here's my simple solution in java

    static long countTriplets(List<Long> arr, long r) {
        
        Map<Long, Long> rightMap = getOccurenceMap(arr);
        Map<Long, Long> leftMap = new HashMap<>();
        long numberOfGeometricPairs = 0;
    
        for (long val : arr) {
          long countLeft = 0;
          long countRight = 0;
          long lhs = 0;
          long rhs = val * r;
          if (val % r == 0) {
            lhs = val / r;
          }
          Long occurence = rightMap.get(val);
          rightMap.put(val, occurence - 1L);

          if (rightMap.containsKey(rhs)) {
            countRight = rightMap.get(rhs);
          }
          if (leftMap.containsKey(lhs)) {
            countLeft = leftMap.get(lhs);
          }
          numberOfGeometricPairs += countLeft * countRight;
          insertIntoMap(leftMap, val);
        }
        return numberOfGeometricPairs;
    }
    
    private static Map<Long, Long> getOccurenceMap(List<Long> test) {
        Map<Long, Long> occurenceMap = new HashMap<>();
        for (long val : test) {
            insertIntoMap(occurenceMap, val);
        }
       return occurenceMap;
    }
  
    private static void insertIntoMap(Map<Long, Long> occurenceMap, Long val) {
        if (!occurenceMap.containsKey(val)) {
            occurenceMap.put(val, 1L);
          } else {
            Long occurence = occurenceMap.get(val);
            occurenceMap.put(val, occurence + 1L);
          }
    }

It really bugs me that all the examples are sorted but the problem description doesn't say that the array has to be sorted, and there's no human to ask if I'm allowed to assume that.

Python Single Traversal:

• Idea is to traverse in the opposite direction of the array, so that division can be avoided.
• Maintain 2 Dictionaries/Hash Maps:
  • map_arr stores the frequency of the numbers encountered yet
  • map_doubles stores the count of 2 sized tuples, which are basically the second and third element of a triplet
• As you go through the array in reverse, either the number encountered will be 1st, 2nd or 3rd number of a triplet it can possibly be a part of.
  • If it were to be the 1st, that means, all the 2nd and 3rd must've been already seen in the array (which are suitable, since problem restriction i < j < k). So from all the doubles in the map_doubles, find the count of doubles that allow the 1st, i.e. x to be such that the triplet looks like (x, x.r, x.r.r).
  • if it were to be the 2nd in the triplet, we would need to find all the 3rd number appropriate found in the map_arr yet.
  • if it were to be the 3rd element, we just need to update in map_arr for that number, so that it can be used as a reference for future doubles.
• Count for all the cases when x is the first element, and return.

def countTriplets(arr, r):
	if len(arr) <= 2:
		return 0
	map_arr = {}
	map_doubles = {}
	count = 0
	# Traversing the array from rear, helps avoid division
	for x in arr[::-1]:

		r_x = r*x
		r_r_x = r*r_x

		# case: x is the first element (x, x*r, x*r*r)
		count += map_doubles.get((r_x, r_r_x), 0)

		# case: x is the second element (x/r, x, x*r)
		map_doubles[(x,r_x)] = map_doubles.get((x,r_x), 0) + map_arr.get(r_x, 0)

		# case: x is the third element (x/(r*r), x/r, x)
		map_arr[x] = map_arr.get(x, 0) + 1
		
	return count