CodingGyan

Contains Nearby Duplicate

easy Arrays

Problem

Print true if two different positions i and j have the same value and the distance between them is at most k (|i - j| <= k). Otherwise print false.

Constraints

  • 1 <= n <= 10^5
  • 0 <= k <= 10^5

Examples

Input

4
1 2 3 1
3

Output

true

Solutions

Best approachTime O(n)Space O(n)

We keep the last position of every value. A repeated value is a hit when the last position is at most k steps back. One pass gives O(n) time.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Nearby duplicate.
 * Input   : n, the array, then k.
 * Output  : true or false.
 * Approach: Last position map.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static boolean solve(int[] a, int k) {
        // Step 1: The map remembers the last position of each value.
        java.util.Map<Integer, Integer> last = new java.util.HashMap<>();
        for (int i = 0; i < a.length; i++) {
            // Step 2: If we saw this value before and it is close enough, we are done.
            Integer previous = last.get(a[i]);
            if (previous != null && i - previous <= k) {
                return true;
            }
            last.put(a[i], i);
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        int k = scanner.nextInt();
        System.out.println(solve(a, k));
    }
}
Hints (2)
  1. Why is only the last position needed?
  2. What is the distance of positions i and j?

Try these next