🔗 The K-th Number

We want to find the k-th number after slicing array from the i-th number to the j-th number and sorting it.

For example, if array is [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3, then

1. Slicing array from the 2nd to the 5th element gives [5, 2, 6, 3].
2. Sorting the array from step 1 gives [2, 3, 5, 6].
3. The 3rd number in the array from step 2 is 5.

Given an array array, and a 2D array commands whose elements are [i, j, k], write a solution function that applies the operation described above to every element of commands and returns the results as an array.

• The length of array is between 1 and 100.
• Each element of array is between 1 and 100.
• The length of commands is between 1 and 50.
• Each element of commands has a length of 3.

Slice [1, 5, 2, 6, 3, 7, 4] from the 2nd to the 5th element, then sort it. The third number in [2, 3, 5, 6] is 5.

Slice [1, 5, 2, 6, 3, 7, 4] from the 4th to the 4th element, then sort it. The first number in [6] is 6.

Slice [1, 5, 2, 6, 3, 7, 4] from the 1st to the 7th element. The third number in [1, 2, 3, 4, 5, 6, 7] is 3.

1. Compute i, j, and k for each element of commands.
2. Slice array from i to j.
3. Sort the sliced array.
4. Find the k-th element of the sliced array.

The algorithm process would look like the above.

JAVA
for (int n = 0; n < answer.length; n++)
{
	int i = commands[n][0];
	int j = commands[n][1];
	int k = commands[n][2];
	
	int length = j - i + 1;
	
	int[] temp = new int[length];
	
	System.arraycopy(array, i - 1, temp, 0, length);
	
	Arrays.sort(temp);
	
	answer[n] = temp[--k];
}

Compute i, j, and k, and find the distance between i and j. Declare an array of that length to hold the slice.

Using the System.arraycopy() method, we can cut out just the desired portion of array into the temp array.

Then sort it, and find the k-th element. Since arrays start at 0, the actual index is k - 1.

JAVA
/**
 * The K-th Number class
 *
 * @author RWB
 * @since 2021.12.10 Fri 21:28:35
 */
class Solution
{
	/**
	 * Method that returns the answer
	 *
	 * @param array: [int[]] array
	 * @param commands: [int[][]] index array
	 *
	 * @return [int[]] the k-th numbers
	 */
	public int[] solution(int[] array, int[][] commands)
	{
		int[] answer = new int[commands.length];
		
		for (int n = 0; n < answer.length; n++)
		{
			int i = commands[n][0];
			int j = commands[n][1];
			int k = commands[n][2];
			
			int length = j - i + 1;
			
			int[] temp = new int[length];
			
			System.arraycopy(array, i - 1, temp, 0, length);
			
			Arrays.sort(temp);
			
			answer[n] = temp[--k];
		}
		
		return answer;
	}
}