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