## DEV Community is a community of 861,926 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Wenqi Jiang

Posted on

# 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


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;
}
}