Circular arrays show up frequently in coding interviews because they test your ability to handle wraparound conditions, indexing with modulo, and apply DSA patterns (stacks, sliding windows, greedy, etc.).
This blog compiles the most asked circular array problems, with explanations and Java implementations.
πΉ 1. Next Greater Element in a Circular Array
Problem: For each element, find the next greater element in circular order. If none exists, return -1
.
import java.util.*;
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < 2 * n; i++) {
int num = nums[i % n];
while (!stack.isEmpty() && nums[stack.peek()] < num) {
res[stack.pop()] = num;
}
if (i < n) stack.push(i);
}
return res;
}
β
Pattern: Monotonic stack.
β
Time: O(n).
πΉ 2. Gas Station (Circular Tour Problem)
Problem: Given gas at each station and cost to travel, find if you can complete a full circular tour.
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return total < 0 ? -1 : start;
}
β
Pattern: Greedy scan.
β
Time: O(n).
πΉ 3. Maximum Sum Circular Subarray
Problem: Find maximum subarray sum in a circular array.
public int maxSubarraySumCircular(int[] nums) {
int total = 0, maxSum = nums[0], curMax = 0, minSum = nums[0], curMin = 0;
for (int n : nums) {
curMax = Math.max(curMax + n, n);
maxSum = Math.max(maxSum, curMax);
curMin = Math.min(curMin + n, n);
minSum = Math.min(minSum, curMin);
total += n;
}
return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
}
β
Pattern: Kadaneβs Algorithm (max + min).
β
Time: O(n).
πΉ 4. Rotate Array (Circular Shift)
Problem: Rotate an array by k
steps to the right.
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
private void reverse(int[] nums, int l, int r) {
while (l < r) {
int temp = nums[l];
nums[l++] = nums[r];
nums[r--] = temp;
}
}
β
Pattern: Reverse trick.
β
Time: O(n).
πΉ 5. Circular Sliding Window Maximum
Problem: Given a circular array and window size k
, return max in each window.
import java.util.*;
public int[] circularSlidingWindowMax(int[] nums, int k) {
int n = nums.length;
int[] extended = new int[2 * n];
System.arraycopy(nums, 0, extended, 0, n);
System.arraycopy(nums, 0, extended, n, n);
Deque<Integer> deque = new ArrayDeque<>();
int[] res = new int[n];
for (int i = 0; i < 2 * n; i++) {
while (!deque.isEmpty() && extended[deque.peekLast()] <= extended[i]) {
deque.pollLast();
}
deque.addLast(i);
if (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
if (i >= k - 1 && i < n + k - 1) {
res[i - k + 1] = extended[deque.peekFirst()];
}
}
return res;
}
β
Pattern: Deque-based sliding window.
β
Time: O(n).
πΉ 6. Josephus Problem (Circular Elimination)
Problem: Eliminate every k-th person until one remains.
public int josephus(int n, int k) {
if (n == 1) return 0;
return (josephus(n - 1, k) + k) % n;
}
β
Pattern: Recursion / DP.
β
Time: O(n).
πΉ 7. Circular Array Loop Detection
Problem: Given jumps in a circular array, check if a cycle exists.
public boolean circularArrayLoop(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
int slow = i, fast = i;
boolean forward = nums[i] > 0;
while (true) {
slow = next(nums, forward, slow);
if (slow == -1) break;
fast = next(nums, forward, fast);
if (fast == -1) break;
fast = next(nums, forward, fast);
if (fast == -1) break;
if (slow == fast) return true;
}
}
return false;
}
private int next(int[] nums, boolean forward, int i) {
boolean dir = nums[i] > 0;
if (dir != forward) return -1;
int n = nums.length;
int next = ((i + nums[i]) % n + n) % n;
if (next == i) return -1;
return next;
}
β
Pattern: Floydβs cycle detection.
β
Time: O(n).
πΉ 8. Shortest Distance in Circular Array
Problem: Find shortest distance between two indices.
public int shortestCircularDistance(int n, int i, int j) {
int diff = Math.abs(i - j);
return Math.min(diff, n - diff);
}
β
Pattern: Math formula.
β
Time: O(1).
πΉ 9. Circular Queue / Deque Design
Problem: Implement a circular deque with insert/delete operations.
class MyCircularDeque {
private int[] data;
private int front, rear, size, capacity;
public MyCircularDeque(int k) {
data = new int[k];
capacity = k;
front = 0;
rear = -1;
size = 0;
}
public boolean insertFront(int value) {
if (isFull()) return false;
front = (front - 1 + capacity) % capacity;
data[front] = value;
size++;
if (rear == -1) rear = front;
return true;
}
public boolean insertLast(int value) {
if (isFull()) return false;
rear = (rear + 1) % capacity;
data[rear] = value;
size++;
return true;
}
public boolean deleteFront() {
if (isEmpty()) return false;
front = (front + 1) % capacity;
size--;
return true;
}
public boolean deleteLast() {
if (isEmpty()) return false;
rear = (rear - 1 + capacity) % capacity;
size--;
return true;
}
public boolean isFull() { return size == capacity; }
public boolean isEmpty() { return size == 0; }
}
β
Pattern: Modular arithmetic.
β
Time: O(1) per operation.
π§ Key Patterns
-
Modulo indexing (
i % n
) β core trick for wraparound. - Extended array trick (concatenate with itself) β useful for sliding windows.
- Kadaneβs Algorithm β max/min subarray in circular arrays.
- Greedy scanning β gas station.
- Cycle detection (Floydβs algo) β circular jumps.
β Final Thoughts
- Circular problems arenβt just about arrays β they show up in scheduling, networking, OS (round robin), and system design.
- Mastering these 8β10 problems covers 90% of interview questions in this domain.
- The secret sauce: always think in modular arithmetic and leverage existing patterns (stack, deque, DP, greedy).
Top comments (0)