HackerRank - Filter huge list for elements that occur more than a given number of times I'm trying to solve this problem on HackerRank, which basically requires the solution to read an input like this (comments are mine)
3                      # the number of cases, each of which consists of a pair of lines below
9 2                    # case 1, the two numbers are N and K
4 5 2 5 4 3 1 3 4      # case 1, the N numbers; filter out those that occur less than K times
9 4                    # case 2
4 5 2 5 4 3 1 3 4      # case 2
10 2                   # case 3
5 4 3 2 1 1 2 3 4 5    # case 3

and the desired output is
4 5 3
-1
5 4 3 2 1

where the second line signifies that there's no number in case 2 which occurs 4 times or more, first and third lines list those elemnts of cases 1 and 3 which all occur the prescribed number of times or more (in this case the threshold is 2 for both case 1 and case 2).
I came up with an algorithmically correct solution, but apparently it has poor performance, as it fails for timeout on this input (expected output)
import Control.Monad (liftM2)
import Data.List (sort,groupBy)
import Data.List (foldl')
main :: IO()
main = do
  nCasesStr &lt;- getLine
  let nCase = read nCasesStr :: Int
  sequence_ $ replicate nCase $ do
    firstLine &lt;- getLine
    secondLine &lt;- getLine
    let [_,k] = asInts $ firstLine
    let list  = asInts $ secondLine      -- LINE A
    let outList = processList k list
    if null outList
      then putStr $ show (-1)
      else mapM_ (putStr . (++&quot; &quot;) . show) outList -- LINE B
    putStrLn &quot;&quot;
    where
      asInt :: String -&gt; Int
      asInt s = read s :: Int
      asInts :: String -&gt; [Int]
      asInts = map asInt . words

processList :: Int -&gt; [Int] -&gt; [Int]
processList k = map fst . filter ((&gt;= k) . snd) . foldl' step []
  where
    step acc@((n,c):ac) val
      | n == val = (n,c + 1):ac
      | otherwise = (n,c):step ac val
    step _ val = [(val,1)]

I'm especially worried about the lines marked as -- LINE A ad -- LINE B: they both traverse the full long input and output lines respectively; then the processList function traverses the input too. Traversing the input only once while spitting out output, however, would not change the BigO complexity, but just reduce it by a factor of 3, am I right?
As regards the processList function, I'm quite happy I had the idea of using a fold (the three of them don't seem to have a consistent difference in performances, as regards the bulk test cases), but maybe I've chosen the wrong stepping function?
Or maybe folding is not the right tool in this case?
It seems that the suggestion I got in the comment is enough to pass the HR test:
import Data.Maybe (fromJust)
import Data.List (foldl', nub)
import qualified Data.Map as M

main :: IO()
main = do
  nCasesStr &lt;- getLine
  let nCase = read nCasesStr :: Int
  sequence_ $ replicate nCase $ do
    k    &lt;- (str2int. last . words) &lt;$&gt; getLine
    list &lt;-    map str2int . words  &lt;$&gt; getLine
    let outList = processList k list
    if null outList
      then putStr $ show (-1)
      else mapM_ (putStr . (++&quot; &quot;) . show) outList
    putStrLn &quot;&quot;
    where
      str2int = read :: String -&gt; Int

processList :: Int -&gt; [Int] -&gt; [Int]
processList k = nub . (filter &lt;$&gt; (flip (\x -&gt; (k &lt;=) . fromJust . M.lookup x . list2map)) &lt;*&gt; id)
  where
    list2map = foldl' step M.empty
    step map num = M.insertWith (+) num 1 map