Gray to Red #1 (Study Journey): Replacing Heavy Array Slicing with (i + 1) % n

Problem Overview: Problem J - Sorted After Rotation

During Hebron Code Jam 2026, I faced Problem J: Sorted After Rotation.

You are given an array a of n distinct integers. You can cyclically shift the entire array to the left by k positions. The goal is to determine if it is possible to make the array strictly increasing after some number of cyclic shifts.

• Input: t test cases, each containing n elements a_1, a_2, \dots, a_n.
• Output: "YES" if a valid cyclic shift exists, "NO" otherwise.

---

What I Learned From This Problem

• Circular Indexing (i + 1) % n: Instead of creating sublists or shifting array elements, (i + 1) % n links the last element back to index 0. This eliminates boundary checks and array slicing.
• Property of Rotated Sorted Arrays: A strictly increasing array that is cyclically shifted has at most 1 drop where a[i] > a[i+1] across its circular boundary.
  • 0 drops: Already sorted.
  • 1 drop: Valid rotated sorted array.
  • >1 drops: Impossible to fix with rotations.
• Avoid Unnecessary Collections: Storing all outputs in an ArrayList<String> before printing creates massive memory overhead and triggers Garbage Collection pauses. Printing directly per testcase is much cleaner.
• Fixing Algorithmic Complexity First: Going from O(N log N) to O(N) time complexity allowed Scanner to pass within generous time limits.

---

Original Implementation (Memory Heavy + O(N \log N))

My first attempt manually split the array, created multiple ArrayList instances, and sorted them to compare equality:

package j;
import java.util.*;

public class J {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        ArrayList<String> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int min = 1;
            int ind = 0;
            int len = scan.nextInt();
            ArrayList<Integer> arr2 = new ArrayList<>();
            for (int j = 0; j < len; j++) {
                arr2.add(scan.nextInt());
                if (arr2.get(j) <= min) {
                    min = arr2.get(j);
                    ind = j; 
                }
            }

            List<Integer> arr5 = arr2.subList(ind, len);
            List<Integer> arr7 = new ArrayList<>();
            List<Integer> arr6 = arr2.subList(0, ind);

            for (int k = 0; k < arr5.size(); k++) {
                arr7.add(arr5.get(k));
            }

            for (int k = 0; k < arr6.size(); k++) {
                arr7.add(arr6.get(k));
            }

            Collections.sort(arr2);
            if (arr2.equals(arr7)){arr.add("YES");}
            else {arr.add("NO");}
        }

        for (int i = 0; i<arr.size() ; i++){System.out.println(arr.get(i));}
    }
}

---

Final Optimized Implementation ($O(N)$ Time)

By replacing array slicing with circular drop counts and primitive arrays, the code becomes concise and fast:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        if (!scan.hasNextInt()) return;
        int t = scan.nextInt();

        while (t-- > 0) {
            int n = scan.nextInt();
            int[] a = new int[n];

            for (int i = 0; i < n; i++) {
                a[i] = scan.nextInt();
            }

            int drops = 0;
            for (int i = 0; i < n; i++) {
                if (a[i] > a[(i + 1) % n]) {
                    drops++;
                }
            }

            if (drops <= 1) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

---

Core Comparison

Aspect	Original Implementation	Final Optimized Implementation
Logic / Strategy	Physical rotation via subList(), merging lists, and calling Collections.sort().	Single linear pass inspecting adjacent elements circularly using (i + 1) % n.
Time Complexity	O(N log N) due to sorting per test case.	O(N) linear time per test case.
Memory Overhead	High memory strain from instantiating multiple ArrayList and subList objects per testcase.	Minimal overhead using primitive int[] array reuse and direct output.
Logical Bug	Hardcoding int min = 1 failed when array elements were strictly larger than 1 (e.g., 10^9).	Removed minimum-element searching entirely; decision is purely based on drop count.