Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Capture as many as possible

    There are n yachts in the ocean at different positions. You are looking at those yachts through stationary binoculars that can capture segments of length L. You’d like to look at as many yachts as possible.
    Knowing that the yachts don’t currently move, what would be the maximum number of yachts you can look at simultaneously with those binoculars?
    notion image

    Input

    The first line of the input contains two integers n (1 ≤ n ≤ ) and L (1 ≤ L ≤ ).
    The next line contains n integers () the positions of yachts.

    Output

    The program should print the maximum number of yachts you can capture with stationary binoculars at once.

    Examples

    Input
    Output
    5 10 11 21 8 18 50
    3

    Explanation

    You can capture the yachts located at 8, 11, 18, or 11, 18, 21.
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue