Problem Description

You have an array nums that can be rotated by a non-negative integer k. When you rotate by k, the array transforms from its original form to [nums[k], nums[k + 1], ... nums[nums.length - 1], nums[0], nums[1], ..., nums[k-1]]. In other words, you take the first k elements and move them to the end of the array.

After rotation, you calculate a score based on how many elements satisfy a specific condition: an element at index i earns one point if its value is less than or equal to i.

For example, given nums = [2,4,1,3,0]:

• If you rotate by k = 2, the array becomes [1,3,0,2,4]
• Now checking each position:
  • Index 0: value 1 > 0 → no point
  • Index 1: value 3 > 1 → no point
  • Index 2: value 0 ≤ 2 → one point
  • Index 3: value 2 ≤ 3 → one point
  • Index 4: value 4 ≤ 4 → one point
• Total score = 3 points

Your task is to find the rotation value k that produces the maximum possible score. If multiple values of k give the same maximum score, return the smallest k.

Intuition

The key insight is to think about when each element contributes a point across different rotations, rather than calculating the entire score for each possible rotation.

For an element nums[i] with value v, we need to determine: for which rotation values k will this element contribute a point? After rotation by k, the element originally at index i moves to position (i - k + n) % n. For this element to score a point, we need v ≤ (i - k + n) % n.

Instead of checking all rotations directly (which would be O(n²)), we can be smarter. For each element, we can calculate the range of k values where it contributes a point. When an element starts contributing and when it stops contributing forms an interval.

The critical observation is that for each element at original position i with value v:

• It starts contributing a point when rotated to a position where its new index is at least v
• The element begins contributing at rotation k = (i + 1) % n
• It stops contributing when the new position becomes less than v, which happens at k = (n + i + 1 - v) % n

By using a difference array technique, we can efficiently track how the score changes as we increase k. We mark the start of each contribution interval with +1 and the end with -1. Then, by scanning through all possible k values and maintaining a running sum, we can find the maximum score and the smallest k that achieves it.

This transforms the problem from calculating full scores for each rotation to simply tracking score changes, reducing complexity from O(n²) to O(n).

Learn more about Prefix Sum patterns.

Solution Approach

The solution uses a difference array to efficiently track score changes across all possible rotations.

Step 1: Initialize the difference array

d = [0] * n

This array tracks the change in score when moving from rotation k-1 to rotation k.

Step 2: Calculate contribution intervals for each element For each element at index i with value v:

l, r = (i + 1) % n, (n + i + 1 - v) % n
d[l] += 1
d[r] -= 1

• l = (i + 1) % n: The rotation where element nums[i] starts contributing a point
• r = (n + i + 1 - v) % n: The rotation where element nums[i] stops contributing
• We increment d[l] to mark the start of contribution
• We decrement d[r] to mark the end of contribution

Step 3: Find the rotation with maximum score

s = 0
mx, ans = -1, n
for k, t in enumerate(d):
    s += t
    if s > mx:
        mx = s
        ans = k

We iterate through all possible rotations k from 0 to n-1:

• s += t: Accumulate the score change to get the actual score at rotation k
• Track the maximum score mx and its corresponding rotation ans
• Since we iterate from small to large k, we automatically get the smallest k when there are ties

Time Complexity: O(n) - We iterate through the array twice (once to build the difference array, once to find the maximum)

Space Complexity: O(n) - For the difference array

The elegance of this approach lies in converting a seemingly O(n²) problem (checking n rotations with n elements each) into an O(n) solution by focusing on when each element's contribution changes rather than recalculating everything from scratch.

Example Walkthrough

Let's walk through the solution with nums = [1, 0, 3, 2].

Step 1: Initialize difference array

d = [0, 0, 0, 0]

Step 2: Process each element to find contribution intervals

For element at index 0, value 1:

• Start contributing: l = (0 + 1) % 4 = 1
• Stop contributing: r = (4 + 0 + 1 - 1) % 4 = 0
• Update: d[1] += 1, d[0] -= 1
• Result: d = [-1, 1, 0, 0]

For element at index 1, value 0:

• Start contributing: l = (1 + 1) % 4 = 2
• Stop contributing: r = (4 + 1 + 1 - 0) % 4 = 2
• Update: d[2] += 1, d[2] -= 1
• Result: d = [-1, 1, 0, 0] (no net change at index 2)

For element at index 2, value 3:

• Start contributing: l = (2 + 1) % 4 = 3
• Stop contributing: r = (4 + 2 + 1 - 3) % 4 = 0
• Update: d[3] += 1, d[0] -= 1
• Result: d = [-2, 1, 0, 1]

For element at index 3, value 2:

• Start contributing: l = (3 + 1) % 4 = 0
• Stop contributing: r = (4 + 3 + 1 - 2) % 4 = 2
• Update: d[0] += 1, d[2] -= 1
• Result: d = [-1, 1, -1, 1]

Step 3: Find maximum score by scanning difference array

Starting with s = 0, mx = -1, ans = 4:

• k=0: s = 0 + (-1) = -1. Since -1 ≤ -1, no update
• k=1: s = -1 + 1 = 0. Since 0 > -1, update mx = 0, ans = 1
• k=2: s = 0 + (-1) = -1. Since -1 ≤ 0, no update
• k=3: s = -1 + 1 = 0. Since 0 ≤ 0, no update

Result: Maximum score is 0, achieved at k = 1.

Verification:

• k=1 rotation: [0, 3, 2, 1]
  • Index 0: 0 ≤ 0 ✓ (1 point)
  • Index 1: 3 > 1 ✗
  • Index 2: 2 ≤ 2 ✓ (1 point)
  • Index 3: 1 ≤ 3 ✓ (1 point)
  • Total: 3 points

Wait, let me recalculate the difference array more carefully:

Actually, the score at k=0 should be the baseline. Let me trace through what happens:

• At k=0 (no rotation): [1, 0, 3, 2]
  • Index 0: 1 > 0 ✗
  • Index 1: 0 ≤ 1 ✓
  • Index 2: 3 > 2 ✗
  • Index 3: 2 ≤ 3 ✓
  • Base score: 2 points

The difference array tracks changes from this baseline as we rotate. When we accumulate the differences starting from 0, we're actually computing the relative score change, not the absolute score. The algorithm still correctly identifies the k with the maximum relative improvement.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of two main parts:

1. First loop iterates through all elements in nums to calculate difference array values - O(n) operations
2. Second loop iterates through the difference array d to find the maximum prefix sum - O(n) operations

Each operation inside both loops (including modulo calculations and array updates) takes O(1) time. Therefore, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses additional space for:

• Difference array d of size n - O(n) space
• A few scalar variables (mx, ans, s, l, r) - O(1) space

The total auxiliary space used is O(n) + O(1) = O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Handling of Circular Range Marking

The Problem: When marking contribution ranges in the difference array, the range can wrap around (i.e., left > right). A common mistake is treating this as a single continuous range instead of two separate ranges.

Incorrect Implementation:

# Wrong: This doesn't handle wraparound correctly
if left <= right:
    diff[left] += 1
    diff[right] -= 1
else:
    # Incorrectly trying to handle wraparound
    diff[left] += 1
    diff[0] += 1  # Wrong!
    diff[right] -= 1

Correct Solution:

# The original code handles this correctly by using modulo arithmetic
diff[left] += 1
diff[right] -= 1

# When right < left, the difference array naturally handles wraparound
# because we're using prefix sum across the entire array

Pitfall 2: Off-by-One Error in Range Calculation

The Problem: The formula for calculating the right boundary (n + i + 1 - v) % n is derived from the inequality v <= (i - k + n) % n. A common mistake is forgetting the +1 or using incorrect boundary logic.

Incorrect Implementation:

# Wrong: Missing the +1
right = (n + i - v) % n  # This would include one rotation too many

# Or wrong: Using inclusive end instead of exclusive
right = (n + i - v) % n
diff[right + 1] -= 1  # This could cause index out of bounds

Correct Solution:

# Correct: The range is [left, right) where right is exclusive
left = (i + 1) % n
right = (n + i + 1 - v) % n  # Note the +1 here
diff[left] += 1
diff[right] -= 1  # Mark the end of the range (exclusive)

Pitfall 3: Forgetting to Handle the Case When v > n

The Problem: When an element's value exceeds the array length (v >= n), it can never contribute to the score regardless of rotation. Some implementations might not handle this edge case properly.

Incorrect Implementation:

# Wrong: Doesn't check if element can ever contribute
for i, v in enumerate(nums):
    left = (i + 1) % n
    right = (n + i + 1 - v) % n  # Could give unexpected results if v > n
    diff[left] += 1
    diff[right] -= 1

Correct Solution:

for i, v in enumerate(nums):
    # Skip elements that can never contribute
    if v >= n:
        continue
  
    left = (i + 1) % n
    right = (n + i + 1 - v) % n
    diff[left] += 1
    diff[right] -= 1

Pitfall 4: Initializing Best Score Incorrectly

The Problem: Starting with max_score = 0 can cause issues if all rotations result in a score of 0, potentially returning an incorrect rotation index.

Incorrect Implementation:

max_score = 0  # Wrong: What if all scores are 0?
best_rotation = 0

for k, delta in enumerate(diff):
    current_score += delta
    if current_score > max_score:  # This might never trigger
        max_score = current_score
        best_rotation = k

Correct Solution:

max_score = -1  # Start with -1 to ensure first valid score is captured
best_rotation = n  # Or 0, but should be set on first iteration

for k, delta in enumerate(diff):
    current_score += delta
    if current_score > max_score:
        max_score = current_score
        best_rotation = k