hey guys, need some help the problem is quite simple:
Given two unsorted arrays team-a and team-b. They may contain duplicates.
For each element in team-b count elements less than or equal to it in array team-a
my solution was:
(defn solution [team-a team-b]
(let [steam-a (sort team-a)
search #(java.util.Collections/binarySearch steam-a %1)
mapper (comp inc search)]
(mapv #(Math/abs (mapper %1)) team-b)))
the problem is , for huge inputs 100K items for team-a and 100K items for team-b array, the solution is taking ~ 150s
the time limit is only 8s, how can I improve the solution ?If (count (distinct team-a))
is small, you can use frequencies and buildup another array with cumulative sums, and make it bit faster.
the bottleneck here is the binarySearch, is taking around 1 ~2 millisecond per call
You might want to turn on reflection checks. It might indicate a lot of time figuring it out. Alternatively, use async-clj-profiler to pinpoint it exactly
Gonna try this @dominicm . Let you know what I found