Problem bank

Problem 244 of 333HardCodingP244

Later days that closed lower

  1. You are given nn daily closing prices p0,…,pn−1p_0, \dots, p_{n-1}. For each day ii, return the number of later days j>ij > i with pj<pip_j < p_i. Checking every pair is O(n2)O(n^2); do it in O(nlog⁡n)O(n \log n). For example, closes [101,99,103,98,100][101, 99, 103, 98, 100] give [3,1,2,0,0][3, 1, 2, 0, 0].