Sort by Permutation

Description

Given a list of strings lst and a list of integers p, reorder lst so that every lst[i] gets placed to p[i].

This should be done in \mathcal{O}(1)O(1) space.

Constraints:

• n ≤ 100,000 where n is the length of lst

Example 1

Input

lst = ["a", "b", "c", "d"]
p = [3, 0, 1, 2]

Output

["b", "c", "d", "a"]

Explanation

a goes to index 3
b goes to index 0
c goes to index 1
d goes to index 2

---

Intuition

quick sort

Implementation

import java.util.*;

class Solution {
    public String[] solve(String[] lst, int[] p) {
        int n = lst.length;
        quickSort(p, 0, n - 1, lst);
        return lst;
    }
    private void quickSort(int[] nums, int l, int r, String[] lst) {
        if (l >= r) {
            return;
        }
        int i = l - 1, j = r + 1, x = nums[i + j >> 1];
        while (i < j) {
            do {
                i++;
            } while (nums[i] < x);
            do {
                j--;
            } while (nums[j] > x);
            if (i < j) {
                swap(nums, i, j, lst);
            }
        }
        quickSort(nums, l, j, lst);
        quickSort(nums, j + 1, r, lst);
    }

    private void swap(int[] nums, int i, int j, String[] lst) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;

        String tempString = lst[i];
        lst[i] = lst[j];
        lst[j] = tempString;
    }
}

Time Complexity

• Time: O(nlogn)
• Space: O(1)

---

import java.util.*;

class Solution {
    public String[] solve(String[] lst, int[] p) {
        int index = 0, n = lst.length;
        while (index < n) {
            // 3 0 1 2
            int originalIndex = p[index]; // originalIndex = 3
            int tempIndex = p[originalIndex]; // tempIndex = 2
            p[originalIndex] = originalIndex; // 3 0 1 3
            p[index] = tempIndex; // 2 0 1 3
            // "a", "b", "c", "d"
            String originalStr = lst[index]; // originalStr = a
            String tempStr = lst[originalIndex]; // tempStr = d
            lst[originalIndex] = originalStr; // a b c a
            lst[index] = tempStr; // d b c a

            if (index == originalIndex) {
                index++;
            }
        }
        return lst;
    }
}