Maximum Cupcakes :
Difficulty Level : Medium
Submissions : 244
Asked In :
Marks :30
: 6 | : 0
You are standing at the start of a very long road straight ahead. On the road, there are $$$n$$$ cupcakes present. You are given the distance of each cupcake from the start of the road. Each of these distances is an integer and multiple cupcakes can be present at the same distance from the start of the road.
You have to select 2 intervals of length $$$k$$$ on the road and collect all cupcakes that lie inside either of the intervals. These intervals are allowed to intersect. For example, if $$$k =3$$$, the interval [ 1,4] is a valid interval of length 3 and by choosing that interval you can collect all the cupcakes that lie at a distance of 1,2,3,4 from the start of the road.
The first line contains $$$n$$$, the number of cupcakes. The second line contains $$$k$$$, the length of the interval. The third line contains an array of n integers. The $$$i_{th}$$$ integer describes the distance of the $$$i_{th}$$$ cupcake from the start of the road, where $$$A_i$$$ is not necessarily distinct. $$$(1 \le n \le 2\cdot10^5)$$$, $$$(1 \le k \le 2\cdot10^9)$$$, $$$(1 \le A_i \le 2\cdot10^9)$$$.
Output a single integer-the maximum number of cupcakes you can collect.
6 1 1 1 2 6 8 9
5
