/*Contains Duplicate II

Given an array of integers and an integer k, find out whether there there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

*/

public class Leetcode2 {

    public static void main(String[] args) {

        int arr[]= {1,2,34,43,1};

        System.out.println(containsNearbyDuplicate(arr,1));

        // TODO Auto-generated method stub

    }

        public static boolean containsNearbyDuplicate(int[] nums, int k) {

                for (int i = 0; i < nums.length - 1; i++) {

                    int temp = k + i;

                    int y = ((temp > nums.length - 1) ? nums.length : temp+1);

                    for (int j = 1; j < y; j++) {

                        int x = ((i+j )> nums.length - 1) ? nums.length-1 : (i+j);

                        if((nums[x] - nums[i])==0)

                            return true;

                    }

                }

                return false;

            }

    /* public static boolean containsNearbyDuplicate(int[] nums, int k) {

         int x;

         for (int i = 0; i < nums.length - 1; i++) {

        int temp = k + i;

     while(temp<=nums.length-1)

     {   int temp2=temp;

     for(int j=i+1;j<temp2;j++) {

         x=nums[j]-nums[i];

         if(x==0)

             return true;

     }

     }

    }

             return false;

     }

*/

}

public class Solution {

    public boolean containsNearbyDuplicate(int[] nums, int k) {

		Map<Integer,Integer> tm=new TreeMap<Integer,Integer>();

			{

				for (int i = 0; i < nums.length ; i++)

				{

				if(tm.containsKey(nums[i]))

				  {

					int j=tm.get(nums[i]);

					if((i-j)<=k)

				 	return true;

				  }

				tm.put(nums[i],i);

			    }

				return false;

			}	

}

}