[Algorithm] Copying slices of an array

// guidelines

1. Always include reasons for choosing certain approach/technology/framework/technique, etc.

2. Before writing a code, summarize the plan in 3 lines, including but not limited to:

- What data structures are we using?

- Time / Space complexity

- What are the edge cases?

 

3. Always leave reasons for failures to find patterns in mistakes. It is helpful in recognizing my weaknesses.

4. Don't cling to a problem that takes more than 30 minutes to solve. Check the answer first, and come back to days later.

  4-1. After you understood the answer, make it yours.

5. When you solved a problem without knowking how you did it, and it occurs repeatedly, it's time to take a step back and grind on one problem. 

Problem Summary

Given an array and a list of commands [i, j, k], for each command: slice from index i to j (1-based), sort the slice, return the kth element (1-based). Collect all results into an array.

My Solution

Approach

Iterates commands, uses Arrays.copyOfRange() + Arrays.sort(), collects results into an ArrayList<Integer>, then converts to int[] via stream.

 

Code (Before)

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        
        List<Integer> list = new ArrayList<>();
        
        for(int[] command:commands){
            //nice use of variables
            int start = command[0]-1; // conversion from 1-based to 0-based index.
            int end = command[1]; // copyOfRange is open in the end: keep 1-based.
            int loc = command[2]-1;
            
            int[] arrayCopy = Arrays.copyOfRange(array, start, end); // variables help understand the intent
            Arrays.sort(arrayCopy);
            list.add(arrayCopy[loc]);
        }
        
        return list.stream()
            .mapToInt(Integer::intValue) // conversion of Integer types to primitive type int using Integer.intValue(); 
            .toArray();
    }
}

 

Strengths:

 

• Named variables (start, end, loc) make the index math readable and self-documenting — easy to verify correctness at a glance.
• Correctly handles 1-based to 0-based index conversion.

 

Limitations (or Trade-offs):

 

• Unnecessary ArrayList + stream conversion. Since commands.length is known upfront, int[] answer = new int[commands.length] is simpler and more efficient. The stream .mapToInt(Integer::intValue).toArray() adds overhead and boxing/unboxing cost.

 

Code (After)

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        
        int[] answer = new int[commands.length];
        
        for(int i = 0; i < commands.length; i++){
            //nice use of variables
            int start = commands[i][0]-1; // conversion from 1-based to 0-based index.
            int end = commands[i][1]; // copyOfRange is open in the end: keep 1-based.
            int loc = commands[i][2]-1;
            
            int[] arrayCopy = Arrays.copyOfRange(array, start, end);
            Arrays.sort(arrayCopy);
            answer[i] = arrayCopy[loc];
        }
        
        return answer;
    }
}

/*
Check if indexes are given as 1-based or 0-based.  
When converting list to arrays of primitive classes, make sure list houses wrapper classes that need to be converted first.
When the length of the final array is known, it is unnecessary and rather inefficient to make a new list only to be unwrapped to an array.
*/

 

Performance Improvements

After code improvement, the performance increased tenfold.

Complexity

 

• Time: O(m · n log n) where m = commands.length, n = max slice length
• Space: O(m) for the list + O(n) for each slice copy

 

 

---

Example

Approach

Same slicing and sorting logic, but collects results directly into a pre-allocated int[].

 

Code

import java.util.Arrays;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        for(int i=0; i<commands.length; i++){
            int[] temp = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
            Arrays.sort(temp);
            answer[i] = temp[commands[i][2]-1];
        }

        return answer;
    }
}

 

Strengths:

 

• Pre-allocated answer array — clean, no boxing/unboxing, no unnecessary conversion.
• Concise and idiomatic for this type of problem.
• Correct index handling throughout.

 

Limitations (or Trade-offs):

Raw index access commands[i][0], commands[i][1], commands[i][2] repeated inline makes it slightly harder to read and more error-prone if the command structure ever changed — named variables would improve this.

 

---

Lessons Learned

 

When the length of the final array is known, it is unnecessary and rather inefficient to make a list only to be unwrapped at the end.
Unwrapping list creats overhead.

 

My Github Repository for Solution Code

https://github.com/ginsengcandy/Coding-Test-Practice/commit/204a4e8c8e074390f399a8b5d7fa2848ec6cec94

[level 1] Title: K번째수, Time: 0.47 ms, Memory: 80 MB -BaekjoonHub · ginsengcandy/Coding-Test-Practice@204a4e8

 

Problem Source

https://school.programmers.co.kr/learn/courses/30/lessons/42748

프로그래머스

 

Resources

https://www.geeksforgeeks.org/java/array-copy-in-java/

Array Copy in Java - GeeksforGeeks

https://montmer27.tistory.com/83

[Java] 리스트를 배열로 변환하기