Problem

A permutation can be specified by an array P, where P[i] represents the location of the element at i in the permutation. For example, [2, 1, 0] represents the permutation where elements at the index 0 and 2 are swapped.

Given an array and a permutation, apply the permutation to the array.

Examples

Example 1

Input: array = ["a", "b", "c"], permutation = [2, 1, 0]
Output: ["c", "b", "a"]
Explanation: The permutation swaps the elements at index 0 and 2, resulting in ["c", "b", "a"].

Solution

Method 1 - Iteration

To apply the permutation to the array:

  1. Create a new array where each element is placed in the position specified by the permutation array.
  2. Iterate through the permutation array and place the corresponding elements from the original array into the new array according to the permutation.

Approach

  1. Initialize a new array of the same length as the input array.
  2. Loop through the permutation array and assign elements from the input array to their new positions as specified by the permutation array.
  3. Return the new array.

Code

Java
public class Solution {
    public String[] applyPermutation(String[] array, int[] permutation) {
        int n = array.length;
        String[] permutedArray = new String[n];
        
        for (int i = 0; i < n; i++) {
            permutedArray[permutation[i]] = array[i];
        }
        
        return permutedArray;
    }

    // Example usage:
    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] result1 = solution.applyPermutation(new String[]{"a", "b", "c"}, new int[]{2, 1, 0});
        System.out.println(Arrays.toString(result1));  // Output: [c, b, a]
        String[] result2 = solution.applyPermutation(new String[]{"apple", "orange", "banana"}, new int[]{2, 0, 1});
        System.out.println(Arrays.toString(result2));  // Output: [banana, apple, orange]
    }
}
Python
class Solution:
    def applyPermutation(self, array: List[str], permutation: List[int]) -> List[str]:
        n = len(array)
        permuted_array = [None] * n
        
        for i in range(n):
            permuted_array[permutation[i]] = array[i]
        
        return permuted_array

# Example usage:
solution = Solution()
print(solution.applyPermutation(["a", "b", "c"], [2, 1, 0]))  # Output: ["c", "b", "a"]
print(solution.applyPermutation(["apple", "orange", "banana"], [2, 0, 1]))  # Output: ["banana", "apple", "orange"]

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array, since we iterate through the permutation array once.
  • 🧺 Space complexity: O(n), for the new array that stores the permuted elements.