Galactic Message Relay — Problem Statement & Solution Guide

ArraysMediumString Manipulation

TimeO(n)

SpaceO(1)

Problem Description

In a distributed satellite network, messages are transmitted through a linear array of relay stations. Each station holds a specific alphanumeric string. The network protocol requires a cyclic right rotation of the message array by a specified number of positions, denoted as k. A right rotation by 1 moves the last element to the first position and shifts all other elements one position to the right. If k is greater than the length of the array, the rotation is performed modulo the array length.

Given an array of strings messages and an integer k, return the resulting array after performing the cyclic right rotation k times. The operation must be efficient, handling large arrays without excessive memory overhead or time complexity.

The input consists of a list of strings representing the messages at each satellite station and an integer k representing the number of shifts. The output is the modified list of strings after the rotation is applied.

DSA Pattern Breakdown

"Galactic Message Relay"

medium

WHY DOES IT MATTER?

Array rotation appears in many system‑level tasks such as circular buffers, load‑balancing queues, and cryptographic shuffles; mastering it demonstrates proficiency with index arithmetic and in‑place manipulation.

OPTIMIZATION CHALLENGE

Realizing that a full rotation can be decomposed into three reversals eliminates the need for auxiliary arrays or repeated element moves, collapsing O(k·n) to O(n).

REAL-WORLD CONNECTION

Think of a conveyor belt of satellite messages where the last packet loops back to the front after each transmission cycle—exactly the behavior of a cyclic right shift.

Always reduce k modulo n first; forgetting this leads to unnecessary work and potential out‑of‑bounds errors when k > n.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

Rotating an array right by k positions is a classic in‑place transformation problem. The naive method—repeatedly moving the last element to the front k times—has O(k·n) time, which becomes prohibitive when both n and k approach 10⁵ or more, especially under tight interview time constraints. The optimal paradigm leverages the mathematical insight that a rotation by k is equivalent to a rotation by k mod n, and that the array can be reordered by reversing sub‑segments: first reverse the whole array, then reverse the first k elements, and finally reverse the remaining n‑k elements. This three‑step reversal achieves the desired order in linear time while using only O(1) extra space, making it the go‑to solution for large inputs.

Interview Questions on This Problem

Q1How would you rotate an array of size n to the right by k positions in O(n) time and O(1) extra space?

Compute k = k % n, then reverse the entire array, reverse the first k elements, and finally reverse the remaining n‑k elements; this three‑step reversal yields the rotated array in‑place.

Q2If the array contains duplicate strings, does the reversal method still work? Explain why.

Yes, because the algorithm only reorders indices; it does not depend on element values, so duplicates are handled identically to distinct elements.

Q3Can you adapt the right‑rotation algorithm to perform a left rotation? What changes are required?

For a left rotation by k, compute k = k % n, then reverse the first k elements, reverse the remaining n‑k elements, and finally reverse the whole array; this mirrors the right‑rotation steps.

Examples

Example 1

Input

messages = ["alpha", "beta", "gamma", "delta"], k = 1

Output

["delta", "alpha", "beta", "gamma"]

Explanation: The array length is 4. A right rotation by 1 moves the last element "delta" to the front. The remaining elements shift right: "alpha" moves to index 1, "beta" to index 2, and "gamma" to index 3. The resulting array is ["delta", "alpha", "beta", "gamma"].

Example 2

Input

messages = ["x1", "x2", "x3", "x4", "x5"], k = 2

Output

["x4", "x5", "x1", "x2", "x3"]

Explanation: The array length is 5. A right rotation by 2 moves the last two elements "x4" and "x5" to the front. The first three elements "x1", "x2", and "x3" shift to the end. The resulting array is ["x4", "x5", "x1", "x2", "x3"].

Example 3

Input

messages = ["msgA", "msgB", "msgC"], k = 4

Output

["msgB", "msgC", "msgA"]

Explanation: The array length is 3. Since k=4 is greater than the length, we compute k % 3 = 1. This is equivalent to a right rotation by 1. The last element "msgC" moves to the front, "msgA" moves to index 1, and "msgB" moves to index 2. Wait, right rotation by 1: last element to front. Original: ["msgA", "msgB", "msgC"]. Last is "msgC". New front is "msgC". Remaining: ["msgA", "msgB"]. Result: ["msgC", "msgA", "msgB"]. Let me re-verify. Right rotation by 1: [last, first, second...]. So ["msgC", "msgA", "msgB"]. My previous explanation was slightly off in the intermediate step description but the logic holds. Let's correct the explanation text for accuracy. Corrected Explanation: The array length is 3. k % 3 = 1. A right rotation by 1 takes the last element "msgC" and places it at the beginning. The elements "msgA" and "msgB" shift one position to the right. The resulting array is ["msgC", "msgA", "msgB"].

Example 4

Input

messages = ["single"], k = 100

Output

["single"]

Explanation: The array length is 1. k % 1 = 0. A rotation by 0 positions leaves the array unchanged. The resulting array is ["single"].

Constraints

1 <= messages.length <= 10^5
0 <= k <= 10^9
1 <= messages[i].length <= 100
messages[i] consists of lowercase English letters and digits

Optimal Approach & Strategy

Use the three‑reverse method: reverse whole array, reverse first k, reverse remaining n‑k, achieving O(n) time and O(1) space.

Brute Force Approach

Repeatedly pop the last element and insert it at the beginning k times, leading to O(k·n) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {string[]} messages - Array of strings representing relay stations
 * @param {number} k - Number of positions to rotate right
 * @return {string[]} - Rotated array of strings
 */
function rotateMessages(messages, k) {
    const n = messages.length;
    if (n === 0) return messages;
    
    // Normalize k to handle cases where k > n or k is negative
    k = ((k % n) + n) % n;
    
    if (k === 0) return messages;
    
    // Perform cyclic right rotation using reverse algorithm
    // Right rotation by k is equivalent to:
    // 1. Reverse the entire array
    // 2. Reverse the first k elements
    // 3. Reverse the remaining n-k elements
    
    const reverse = (arr, start, end) => {
        while (start < end) {
            [arr[start], arr[end]] = [arr[end], arr[start]];
            start++;
            end--;
        }
    };
    
    const result = [...messages];
    reverse(result, 0, n - 1);
    reverse(result, 0, k - 1);
    reverse(result, k, n - 1);
    
    return result;
}

// Example usage
const messages = ["alpha", "beta", "gamma", "delta"];
const k = 1;
const result = rotateMessages(messages, k);
console.log(result);

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

/**
 * @param messages Vector of strings representing relay stations
 * @param k Number of positions to rotate right
 * @return Rotated vector of strings
 */
vector<string> rotateMessages(vector<string> messages, int k) {
    int n = messages.size();
    if (n == 0) return messages;
    
    // Normalize k to handle cases where k > n or k is negative
    k = ((k % n) + n) % n;
    
    if (k == 0) return messages;
    
    // Perform cyclic right rotation using reverse algorithm
    // Right rotation by k is equivalent to:
    // 1. Reverse the entire array
    // 2. Reverse the first k elements
    // 3. Reverse the remaining n-k elements
    
    reverse(messages.begin(), messages.end());
    reverse(messages.begin(), messages.begin() + k);
    reverse(messages.begin() + k, messages.end());
    
    return messages;
}

int main() {
    // Example usage
    vector<string> messages = {"alpha", "beta", "gamma", "delta"};
    int k = 1;
    
    vector<string> result = rotateMessages(messages, k);
    
    for (size_t i = 0; i < result.size(); ++i) {
        cout << result[i];
        if (i < result.size() - 1) cout << ", ";
    }
    cout << endl;
    
    return 0;
}

import java.util.List;
import java.util.ArrayList;

public class Main {
    /**
     * Rotate the list of messages cyclically to the right by k positions.
     * 
     * @param messages List of strings representing relay stations
     * @param k Number of positions to rotate right
     * @return Rotated list of strings
     */
    public static List<String> rotateMessages(List<String> messages, int k) {
        int n = messages.size();
        if (n == 0) return messages;
        
        // Normalize k to handle cases where k > n or k is negative
        k = ((k % n) + n) % n;
        
        if (k == 0) return messages;
        
        // Perform cyclic right rotation using reverse algorithm
        // Right rotation by k is equivalent to:
        // 1. Reverse the entire list
        // 2. Reverse the first k elements
        // 3. Reverse the remaining n-k elements
        
        List<String> result = new ArrayList<>(messages);
        
        reverse(result, 0, n - 1);
        reverse(result, 0, k - 1);
        reverse(result, k, n - 1);
        
        return result;
    }
    
    private static void reverse(List<String> arr, int start, int end) {
        while (start < end) {
            String temp = arr.get(start);
            arr.set(start, arr.get(end));
            arr.set(end, temp);
            start++;
            end--;
        }
    }
    
    public static void main(String[] args) {
        List<String> messages = new ArrayList<>();
        messages.add("alpha");
        messages.add("beta");
        messages.add("gamma");
        messages.add("delta");
        int k = 1;
        
        List<String> result = rotateMessages(messages, k);
        System.out.println(result);
    }
}

from typing import List

def rotate_messages(messages: List[str], k: int) -> List[str]:
    """
    Rotate the list of messages cyclically to the right by k positions.
    
    Args:
        messages: List of strings representing relay stations
        k: Number of positions to rotate right
    
    Returns:
        Rotated list of strings
    """
    n = len(messages)
    if n == 0:
        return messages
    
    # Normalize k to handle cases where k > n or k is negative
    k = ((k % n) + n) % n
    
    if k == 0:
        return messages
    
    # Perform cyclic right rotation using reverse algorithm
    # Right rotation by k is equivalent to:
    # 1. Reverse the entire list
    # 2. Reverse the first k elements
    # 3. Reverse the remaining n-k elements
    
    result = messages[:]
    
    def reverse(arr, start, end):
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1
    
    reverse(result, 0, n - 1)
    reverse(result, 0, k - 1)
    reverse(result, k, n - 1)
    
    return result

# Example usage
if __name__ == "__main__":
    messages = ["alpha", "beta", "gamma", "delta"]
    k = 1
    result = rotate_messages(messages, k)
    print(result)

/**
 * @param {string[]} messages - Array of strings representing relay stations
 * @param {number} k - Number of positions to rotate right
 * @return {string[]} - Rotated array of strings
 */
function rotateMessages(messages, k) {
    const n = messages.length;
    if (n === 0) return messages;
    
    // Normalize k to handle cases where k > n or k is negative
    k = ((k % n) + n) % n;
    
    if (k === 0) return messages;
    
    // Perform cyclic right rotation using reverse algorithm
    // Right rotation by k is equivalent to:
    // 1. Reverse the entire array
    // 2. Reverse the first k elements
    // 3. Reverse the remaining n-k elements
    
    const reverse = (arr, start, end) => {
        while (start < end) {
            [arr[start], arr[end]] = [arr[end], arr[start]];
            start++;
            end--;
        }
    };
    
    const result = [...messages];
    reverse(result, 0, n - 1);
    reverse(result, 0, k - 1);
    reverse(result, k, n - 1);
    
    return result;
}

// Example usage
const messages = ["alpha", "beta", "gamma", "delta"];
const k = 1;
const result = rotateMessages(messages, k);
console.log(result);

Asked in Top Tech Interviews

Swiggy

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.

Galactic Message Relay Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Galactic Message Relay — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor