New Year Chaos

  • + 0 comments

    Java (Not a Sort Solution)

        public static void minimumBribes(List<Integer> q) {
            // Record how many numbers before the current element are larger than the element itself. The count will be stored in the check array at the corresponding index.
    
            //For example, given the array [1, 2, 4, 5, 3]:
            //For the element 3 (at index 4), there are two elements (4 and 5) that are larger and appear before it.
            //Therefore, check[4] = 2.
            int[] check = new int[q.size() + 1];
            Arrays.fill(check, 0);
    
            int res = 0;
            for (int i = 0 ; i < q.size() ; i++) {
                int n = q.get(i);
                
                for (int j = 1 ; j < n ; j++){
                    check[j]++;
                }
                
                int ori = n - 1;
                int t = ori - i;
                
                if (t > 2) {
                    res = -1;
                    break;
                }
                if (t <= 0) {
                    t =  check[n] + t;  
                }
                res += t;    
            }
            System.out.println(res > 0 ? res : "Too chaotic");
        }