Array Transformation Under Cyclic Shifts — Problem Statement & Solution Guide

ArraysMediumcyclicity and pattern recognition

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Array Transformation Under Cyclic Shifts problem optimally.

TopicArrays

Patterncyclicity and pattern recognition

TimeO(n)

SpaceO(1)

Problem Description

Array Transformation Under Cyclic Shifts

You are given an array of integers nums and an integer k. In one operation you may either (1) move the last element of the array to the front (a cyclic right shift by one position) or (2) reverse the entire array. After performing exactly k operations, you must obtain the lexicographically smallest possible array. Your task is to output that minimal array.

Input format: the first line contains two integers n and k, the length of the array and the number of operations. The second line contains n integers representing nums.

Output format: output the lexicographically smallest array that can be achieved after exactly k operations, as n space‑separated integers on a single line.

DSA Pattern Breakdown

"Array Transformation Under Cyclic Shifts"

medium

WHY DOES IT MATTER?

Understanding operation parity and modular reduction is crucial for many transformation problems where a small set of actions can be composed arbitrarily. It prevents exponential blow‑up and reveals hidden constant‑size state spaces.

OPTIMIZATION CHALLENGE

The key insight is that the sequence of operations collapses to two parameters: reversal parity (0/1) and net shift amount modulo n. This reduces the search space from O(2^k) to O(1) candidates, enabling a linear scan to pick the lexicographically smallest array.

REAL-WORLD CONNECTION

Think of a distributed log replication system where you can either rotate the log (cyclic shift) or take a snapshot (reverse). Deciding the minimal state after a fixed number of maintenance steps mirrors this array transformation logic.

During an interview, first write down the algebraic properties of each operation (inverse, commutation) before coding. A quick parity check often unlocks the optimal solution for seemingly complex operation sequences.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The two allowed operations—cyclic right shift and full reversal—form a small transformation group on the array. Because a reversal is its own inverse, any sequence of operations can be reduced to at most one reversal (parity of reversals matters) and a number of right‑shifts. The exact count of right‑shifts is determined by how many of the k steps are allocated to shifts after accounting for the possible single reversal. Since shifting n positions yields the original ordering, the effective shift amount is taken modulo the array length. Consequently, the problem collapses to evaluating at most two candidate arrays: (1) the original array right‑shifted by k mod n, and (2) the reversed array right‑shifted by (k‑1) mod n (if a reversal is used). The lexicographically smallest of these candidates is the answer. Naïve brute‑force simulation of all 2^k operation sequences explodes exponentially and is infeasible for n ≈ 10^5 and k ≈ 10^9, whereas the group‑theoretic reduction yields a linear‑time solution.

The optimal paradigm leverages parity analysis and modular arithmetic. By observing that the order of a single reversal relative to shifts only changes the direction of the subsequent shifts, we can translate any mixed sequence into one of the two canonical forms mentioned above. This insight eliminates the need for dynamic programming or BFS over states, reducing both time and space to O(n). The approach exemplifies how algebraic reasoning about operation properties can turn an apparently combinatorial explosion into a constant‑factor enumeration of possibilities.

Interview Questions on This Problem

Q1How would you handle the case when k is larger than the array length n?

Because a cyclic right shift by n positions restores the original order, we take the shift count modulo n. For the scenario with a reversal, we compute (k‑1) mod n for the remaining shifts after using one operation for the reversal.

Q2Why is it sufficient to consider at most one reversal in the optimal solution?

A reversal is an involution (applying it twice returns to the original state), so any even number of reversals cancels out. Hence only the parity of reversals matters, giving either 0 or 1 effective reversal.

Q3Can you extend this solution to support a left‑shift operation instead of a right‑shift? How would the algorithm change?

A left‑shift is equivalent to a right‑shift by n‑1 positions. The same parity‑based reduction applies; we just adjust the effective shift amount to (k mod n) for left‑shifts or (n‑(k mod n)) for right‑shifts, and compute the candidate arrays accordingly.

Examples

Example 1

Input

5 2
3 1 4 1 5

Output

1 4 1 3 5

Explanation: All 2‑operation sequences are considered. The sequence Shift then Reverse yields [1,4,1,3,5], which is lexicographically smaller than any other result.

Example 2

Input

4 1
2 3 1 4

Output

4 1 3 2

Explanation: With one operation, the two possibilities are Shift → [4,2,3,1] and Reverse → [4,1,3,2]. The latter is lexicographically smaller because its second element 1 is less than 2.

Example 3

Input

3 3
1 2 3

Output

1 2 3

Explanation: Enumerating all 8 sequences of 3 operations shows that the original array [1,2,3] is the smallest achievable result.

Constraints

Array length will be between 3 and 1000 elements.
The number of operations will range from 1 to 10^5.

Optimal Approach & Strategy

Reduce the problem to at most two candidate arrays by using parity of reversals and modular arithmetic for shifts, then compare them.

Brute Force Approach

Enumerate all possible sequences of k operations (2^k possibilities) and simulate each to track the final array.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var transform = function(nums, k) {
    const n = nums.length;
    const shift = k % n;
    const res = new Array(n);
    for (let i = 0; i < n; i++) {
        res[(i + shift) % n] = nums[i];
    }
    return res;
};

class Solution {
public:
    vector<int> transform(vector<int>& nums, int k) {
        int n = nums.size();
        int shift = k % n;
        vector<int> res(n);
        for (int i = 0; i < n; ++i) {
            res[(i + shift) % n] = nums[i];
        }
        return res;
    }
};

class Solution {
    public int[] transform(int[] nums, int k) {
        int n = nums.length;
        int shift = k % n;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[(i + shift) % n] = nums[i];
        }
        return res;
    }
}

class Solution:
    def transform(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        shift = k % n
        res = [0] * n
        for i in range(n):
            res[(i + shift) % n] = nums[i]
        return res

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var transform = function(nums, k) {
    const n = nums.length;
    const shift = k % n;
    const res = new Array(n);
    for (let i = 0; i < n; i++) {
        res[(i + shift) % n] = nums[i];
    }
    return res;
};

Asked in Top Tech Interviews

PhonePePayPal

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.