fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5.  
  6. class Ideone {
  7. 	static int COLORS_EXISTS = 10;
  8.  
  9.     static class Interval {
  10.         int l, r;
  11.  
  12.         public Interval(int l, int r) {
  13.             this.l = l;
  14.             this.r = r;
  15.         }
  16.  
  17.         int length() {
  18.             return Math.abs(r - l);
  19.         }
  20.     }
  21.  
  22.     static Interval getMinAllColorsSubArray(int[] arr) {
  23.         int r = -1; 
  24.         int l = 0;
  25.         HashMap<Integer, Integer> colorsCount = new HashMap<>();
  26.         int differentColorsCount = 0;
  27.         Interval minSubArrayBounds = null;
  28.  
  29.         while (differentColorsCount < COLORS_EXISTS && r < arr.length - 1) {
  30.             r++;
  31.             int rCol = arr[r];
  32.             if (!colorsCount.containsKey(rCol)) {
  33.                 differentColorsCount++;
  34.                 colorsCount.put(rCol, 1);
  35.             } else {
  36.                 colorsCount.merge(rCol, 1, Integer::sum);
  37.             }
  38.  
  39.             while (colorsCount.containsKey(arr[l]) && colorsCount.get(arr[l]) > 1) {
  40.             	colorsCount.merge(arr[l], -1, Integer::sum);
  41.                 l++;
  42.             }
  43.  
  44.             if (differentColorsCount == COLORS_EXISTS) {
  45.                 Interval subArrayBounds = new Interval(l, r);
  46.                 if (minSubArrayBounds == null || minSubArrayBounds.length() > subArrayBounds.length()) {
  47.                     minSubArrayBounds = subArrayBounds;
  48.                 }
  49.             }
  50.         }
  51.  
  52.         return minSubArrayBounds;
  53.     }
  54.  
  55. 	public static void main (String[] args) throws java.lang.Exception
  56. 	{
  57. 		int[] input = new int[]{1, 2, 3, 1, 1, 2, 1, 3, 2, 4, 5, 6, 7, 8, 9, 0, 0, 3, 4, 3, 9, 0};
  58. 		Interval res = getMinAllColorsSubArray(input);
  59. 		System.out.println(res.l + " " + res.r);
  60. 	}
  61. }
Success #stdin #stdout 0.1s 36112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6 15
https://ideone.com/netAAY
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!