fork download
  1. import java.util.*;
  2.  
  3. public class Main {
  4. public static void main(String[] args) {
  5.  
  6. Scanner sc = new Scanner(System.in);
  7.  
  8. int n = sc.nextInt();
  9. int[] arr = new int[n];
  10.  
  11. for(int i = 0; i < n; i++) {
  12. arr[i] = sc.nextInt();
  13. }
  14.  
  15. int L = sc.nextInt();
  16. int R = sc.nextInt();
  17.  
  18. int required = R - L + 1;
  19.  
  20. Map<Integer,Integer> freq = new HashMap<>();
  21.  
  22. int distinct = 0;
  23. int left = 0;
  24. int ans = Integer.MAX_VALUE;
  25.  
  26. // arr = 1 2 2 3 2 4 5 5 3 4 6 and l = 3, r = 5 i need to catch 5, 3, 4
  27. // i have to be able to move on from local min(3,2,4,5), i also need to make sure only the elements
  28. // i care about are in window, if i find a good satisfying window,
  29. // i still need to move on from it n explore others
  30. for(int right = 0; right < n; right++) {
  31. if(arr[right] >= L && arr[right] <= R) {
  32. freq.put(arr[right], freq.getOrDefault(arr[right], 0) + 1);
  33. if(freq.get(arr[right]) == 1) {
  34. distinct++;
  35. }
  36. }
  37. //we want to maintain the window in hashmap, i only insert the elem from l to r and if the size of hashmap
  38. // is l-r+1 then we found a window where all l to r present, now just count the length of window
  39. // and start to remove the elem that r in window >l and <r so we can find some new window within the window
  40. // if we find a new window within window then its smaller and will be counted coz of while condition
  41. // since distinct still = required
  42. while(distinct == required){
  43. ans = Math.min(ans, right-left+1);
  44. if(arr[left] >= L && arr[left] <= R) {
  45. freq.put(arr[left], freq.get(arr[left]) - 1);
  46. if(freq.get(arr[left]) == 0) {
  47. freq.remove(arr[left]);
  48. distinct--;
  49. }
  50. }
  51. left++; // inc window to explore new
  52. }
  53. }
  54. System.out.println(ans);
  55. }
  56. }
Success #stdin #stdout 0.11s 56500KB
stdin
11
1 2 2 3 2 4 5 5 3 4 6
3 5
stdout
3