acqcc

1389. Create Target Array in the Given Order

Jun 06, 20222 min read

Problem Statement

Pattern:

Solution

O(n^2) solution

public int[] createTargetArray (int[] nums, int[] index){
	// create target arr
	int[] target = new int[nums.length];
	// insert from the end
	int i = 0, j = 0;
	// while index has not ended
	for (i = 0; i < index.length; i++) {
		// end -> start till j has not reached index[i]
		for (j = target.length-1; j > index[i]; j--) {
			// shift el fwd
			target[j] = target[j-1];
		}
		// insert num at j index
		target[j] = nums[i];
	}
	return target;
}

Notes

  • Start from the back and shift all elements fwd till target index has been reached.
  • Insert num at target index.
  • Works for all cases, whether its a new indes, or a prewritten index, end of the array, start of the array.
public int[] createTargetArrayShort (int[] nums, int[] index){
	ArrayList<Integer> target = new ArrayList<>(nums.length);
	for (int i = 0; i < index.length; i++) {
		target.add(index[i], nums[i]);
	}
	// returns an int[] array instead of ArrayList<Integer>
	return target.stream().mapToInt(Integer::intValue).toArray();
	// target.stream() returns a stream with collection 'target' as source
	// mapToInt returns an IntStream after appying necessary modifications (unboxing int from Integer in this case)
	// toArray() converts stream to array
}

Notes

Graph

Backlinks