Count Good Cyclic Rotations - Medium Solution

The problem

You are given an integer array nums of even length n.

A cyclic rotation of nums is obtained by choosing a prefix of nums whose length is between 0 and n - 1 (inclusive), and moving it to the end of the array while preserving the order of all elements.

A cyclic rotation is good if the sum of its first n / 2 elements is strictly greater than the sum of its last n / 2 elements.

Return the number of cyclic rotations of nums that are good.

Example 1:

Input: nums = [1,2,3,4,5,6]

Output: 3

Explanation:

The cyclic rotations of nums are:

Cyclic rotation	Sum of first `n / 2` elements	Sum of last `n / 2` elements
`[1, 2, 3, 4, 5, 6]`	`1 + 2 + 3 = 6`	`4 + 5 + 6 = 15`
`[2, 3, 4, 5, 6, 1]`	`2 + 3 + 4 = 9`	`5 + 6 + 1 = 12`
`[3, 4, 5, 6, 1, 2]`	`3 + 4 + 5 = 12`	`6 + 1 + 2 = 9`
`[4, 5, 6, 1, 2, 3]`	`4 + 5 + 6 = 15`	`1 + 2 + 3 = 6`
`[5, 6, 1, 2, 3, 4]`	`5 + 6 + 1 = 12`	`2 + 3 + 4 = 9`
`[6, 1, 2, 3, 4, 5]`	`6 + 1 + 2 = 9`	`3 + 4 + 5 = 12`

The first half has a greater sum than the second half for 3 rotations. Thus, the answer is 3.

Example 2:

Input: nums = [1,2,1,2]

Output: 0

Explanation:

The cyclic rotations of nums are:

Cyclic rotation	Sum of first `n / 2` elements	Sum of last `n / 2` elements
`[1, 2, 1, 2]`	`1 + 2 = 3`	`1 + 2 = 3`
`[2, 1, 2, 1]`	`2 + 1 = 3`	`2 + 1 = 3`
`[1, 2, 1, 2]`	`1 + 2 = 3`	`1 + 2 = 3`
`[2, 1, 2, 1]`	`2 + 1 = 3`	`2 + 1 = 3`

No cyclic rotation is good because the two sums are equal for every rotation. Thus, the answer is 0.

Constraints:

2 <= n == nums.length <= 10⁵
1 <= nums[i] <= 10⁹
n is even.

Approach overview

Problem Overview: Given an array of integers, count how many cyclic rotations are considered "good" according to a specific rule—for example, all prefix sums remain non-negative or the array becomes non-decreasing. The naive method checks every rotation individually, leading to O(n²) work.

Approach 1: Brute Force (O(n²) time, O(1) space)

For each of the n possible rotations, simulate the rotation by iterating through the array starting from each index and verify the condition from scratch. This repeats many calculations and is only feasible for small arrays.

Approach 2: Sliding Window (O(n) time, O(1) space)

The key insight is to avoid rechecking from scratch by maintaining the condition incrementally as you slide the window across the doubled array (concatenate the array with itself). Use two pointers or a deque to track relevant statistics—like prefix sums or minimum values—so each element enters and leaves the window exactly once.

Recommended for interviews: Interviewers expect you to recognize that brute force is too slow for large inputs. The sliding window solution demonstrates your ability to reuse computations and reduce time complexity from quadratic to linear. Start by explaining brute force to show understanding, then pivot to the optimized approach.

Solution

Let n be the length of the array and m = n / 2. First compute the sum l of the first m elements of the original array and the sum r of the last m elements. If l > r, increment the answer by 1.

Then start from the original array and cyclically shift it left by one position, n - 1 times in total. On the i-th shift (i starts from 0), the first half loses nums[i] and gains nums[(i + m) bmod n], while the second half does the opposite. Update l and r in O(1) time, and increment the answer whenever l > r.

The time complexity is O(n) and the space complexity is O(1), where n is the length of the array nums.

Python

class Solution:
    def countGoodRotations(self, nums: list[int]) -> int:
        n = len(nums)
        m = n // 2
        l = sum(nums[:m])
        r = sum(nums[m:])
        ans = int(l > r)
        for i in range(n - 1):
            l -= nums[i]
            r += nums[i]
            l += nums[(i + m) % n]
            r -= nums[(i + m) % n]
            ans += int(l > r)
        return ans

Java

class Solution {
    public int countGoodRotations(int[] nums) {
        int n = nums.length;
        int m = n / 2;

        long l = 0, r = 0;
        for (int i = 0; i < m; i++) {
            l += nums[i];
        }
        for (int i = m; i < n; i++) {
            r += nums[i];
        }

        int ans = l > r ? 1 : 0;

        for (int i = 0; i < n - 1; i++) {
            l -= nums[i];
            r += nums[i];
            l += nums[(i + m) % n];
            r -= nums[(i + m) % n];
            ans += l > r ? 1 : 0;
        }

        return ans;
    }
}

C++

class Solution {
public:
    int countGoodRotations(vector<int>& nums) {
        int n = nums.size();
        int m = n / 2;

        long long l = 0, r = 0;
        for (int i = 0; i < m; i++) {
            l += nums[i];
        }
        for (int i = m; i < n; i++) {
            r += nums[i];
        }

        int ans = l > r;

        for (int i = 0; i < n - 1; i++) {
            l -= nums[i];
            r += nums[i];
            l += nums[(i + m) % n];
            r -= nums[(i + m) % n];
            ans += l > r;
        }

        return ans;
    }
};

TypeScript

function countGoodRotations(nums: number[]): number {
    const n = nums.length;
    const m = Math.floor(n / 2);

    let l = 0,
        r = 0;
    for (let i = 0; i < m; i++) {
        l += nums[i];
    }
    for (let i = m; i < n; i++) {
        r += nums[i];
    }

    let ans = l > r ? 1 : 0;

    for (let i = 0; i < n - 1; i++) {
        l -= nums[i];
        r += nums[i];
        l += nums[(i + m) % n];
        r -= nums[(i + m) % n];
        ans += l > r ? 1 : 0;
    }

    return ans;
}

func countGoodRotations(nums []int) int {
	n := len(nums)
	m := n / 2

	var l, r int64
	for i := 0; i < m; i++ {
		l += int64(nums[i])
	}
	for i := m; i < n; i++ {
		r += int64(nums[i])
	}

	ans := 0
	if l > r {
		ans++
	}

	for i := 0; i < n-1; i++ {
		l -= int64(nums[i])
		r += int64(nums[i])
		l += int64(nums[(i+m)%n])
		r -= int64(nums[(i+m)%n])
		if l > r {
			ans++
		}
	}

	return ans
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force	O(n²)	O(1)	Small inputs or when clarity beats performance
Sliding Window	O(n)	O(1)	General case; optimal for large arrays

Frequently asked questions

Is Count Good Cyclic Rotations easy or hard?

It is rated Medium difficulty on FleetCode with a ~49% acceptance rate, indicating it requires moderate problem-solving skills.

Count Good Cyclic Rotations Python/Java solution

Implementations are available on FleetCode in Python, Java, C++, Go, and TypeScript using the sliding window method.

How to solve Count Good Cyclic Rotations in O(n)?

Concatenate the array with itself and use two pointers to slide a window of length n. Maintain running statistics like prefix sums or minimums to check the condition in constant time per step.

What is the best approach for Count Good Cyclic Rotations?

The optimal approach uses sliding window technique to achieve O(n) time complexity by maintaining the condition incrementally over a doubled array.

Is Count Good Cyclic Rotations asked at Google/Amazon/Meta?

While not confirmed for specific companies, similar array rotation problems appear frequently at top tech firms like Google and Amazon.

What data structure is used in Count Good Cyclic Rotations?

The sliding window approach typically uses two pointers or a deque to maintain the current window state efficiently.

What is the time complexity of Count Good Cyclic Rotations?

The brute force solution runs in O(n²), but with sliding window you can solve it in O(n) time and O(1) extra space.

Count Good Cyclic Rotations solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Count Good Cyclic Rotations solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems