Preparing for an interview? Check out Cracking the Coding Interview
Published on

k-spike in stock price list

Author
  • Shared Anonymously

Given a price array prices, count the number of k-spikes in prices, k-spikes means for index i,

  • there are at least k prices (do not need to be continuous) before i that are smaller than prices[i], AND
  • there are at lesat k prices (do not need to be continuous) after i that are smaller than prices[i]

There is at least one k-spike in the test cases.

  • 1 <= i <= 2*10^5
  • 1<=prices[i] < 10^5
  • 1<=k<=3
def num_k_spikes(prices:List, k:int):  
pass

I tried a naive solution with O(N^2) and got TLE. Then I tried to solve using prefix and suffix but failed to figure it out, finally I realized maybe I can try max_heap, but I didn't have enough time, can someone help me with this?

ref: https://stackoverflow.com/q/76856312/6888630

Report • Mark as Helpful