[Algorithm] Custom arrange String arrays

// 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 it after 2 days. After you understood the answer, make it yours.

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

Problem

Original Problem (Translated)

Given a list of strings strings and an integer n, sort the strings in ascending order based on the character at index n of each string.

For example, if strings is ["sun", "bed", "car"] and n is 1, the characters at index 1 of each word are "u", "e", "a" respectively, so strings should be sorted based on those characters.

Constraints

strings has a length between 1 and 50. Each element of strings consists of lowercase alphabetic characters. Each element of strings has a length between 1 and 100. The length of every element in strings is greater than n. If multiple strings share the same character at index n, they should be ordered lexicographically (alphabetical order of the full string).

Example

The characters at index 1 of "sun", "bed", "car" are "u", "e", "a" respectively. Sorting by these characters gives ["car", "bed", "sun"].

 

Schemes - 1
Use something like Comparator.comparingChar(word -> word.charAt(n));
This will automatically rearrange the elements based on their (n)th character.
But Comparator.comparingChar() doesn't exist, so we have to use Comparator.comparingInt()

- What data structures are we using?
Arrays
Reason: Sorting non-primitive types(String), time complexity is equal to Collections.sort() -> Tim Sort. Converting to Collections results in unnecessary memory allocations.

- Time / Space complexity
Average : O(n)

- What are the edge cases?
None (I guess)

 

1st Attempt:
Result: Answer is always an empty array.
- Mistake #1
Forgot to allocate the computed value to the final answer
- Mistake #2
Missed secondary sort for tie-breaking
- Mistake #3
Missed type declaration in the lambda expression(String s -> s.charAt(n)), resulted in compile error
-> This is due to Generic type inference limitation, which will be further addressed in later posts.

 

My Solution (Key Idea: Comparator.comparingInt())

import java.util.*;

class Solution {
    public String[] solution(String[] strings, int n) {
        Arrays.sort(strings, 
                    Comparator.comparingInt((String s) -> s.charAt(n))
                   .thenComparing(Comparator.naturalOrder()));
        return strings;
    }
}
/*
References
Arrays.sort()는 배열을 오름차순(작은 값 → 큰 값)으로 정렬합니다.
객체 배열을 정렬할 때는 Comparator를 이용해 정렬 기준을 직접 정의할 수 있습니다.
Arrays.sort(people, Comparator.comparingInt(p -> p.age));
출처: https://hianna.tistory.com/922 [어제 오늘 내일:티스토리]
*/

 

Strengths:

1. Concise and readable
The entire logic fits in one expression. Someone familiar with Java's Comparator API can understand the intent immediately.

2. Correct two-level sorting
Properly handles the tie-breaking condition with .thenComparing(Comparator.naturalOrder()) — many people miss this.

3. Type annotation in the right place
(String s) is placed exactly where it's needed to resolve the type inference issue, without over-specifying elsewhere.

4. In-place sort, no extra space
Returning strings directly instead of copying into a new array is clean and memory-efficient.

 

Limitations (or Trade-offs):

1. Mutates the input array
Arrays.sort() sorts strings in-place. If the caller didn't expect their original array to be modified, this could cause subtle bugs in a real codebase.

// Defensive approach if immutability matters:
String[] copy = strings.clone();
Arrays.sort(copy, ...);
return copy;

2. No boundary validation
The constraints guarantee n is always a valid index, so it's fine for this problem — but in production code, accessing s.charAt(n) without checking n < s.length() would throw StringIndexOutOfBoundsException.

3. naturalOrder() compares the full string, not just from index n
This actually matches the problem's requirement, but it's worth being conscious that .thenComparing(Comparator.naturalOrder()) sorts by the entire string, not just the suffix after index n. For this problem it doesn't matter, but in a variation of the problem it could produce unexpected results.

 

---

Example (Key Idea: take nth char as a temporary prefix)

import java.util.*;

class Solution {
    public String[] solution(String[] strings, int n) {
        String[] answer = {};
        ArrayList<String> arr = new ArrayList<>();
        for (int i = 0; i < strings.length; i++) {
            arr.add("" + strings[i].charAt(n) + strings[i]); 
        } // copy nth character to the beginning of the word
        // creative but creates new Strings in every iteration. O(n) time & space complexity
        Collections.sort(arr); //arranged the strings without modifying sorting methods -> O(nlogn) time complexity
        answer = new String[arr.size()]; // Redundant. Could've allocated earlier. O(n) space complexity
        for (int i = 0; i < arr.size(); i++) {
            answer[i] = arr.get(i).substring(1, arr.get(i).length()); // Code hard to read & hard-coded 1 makes it vulnerable to changes in conditions.
        } //O(n) time complexity
        return answer;
    }
}

 

Strengths:

- Overall, O(nlogn) time complexity and O(n) space complexity.

- Copying nth character as the prefix for the intermediate array was clever. When there occurs a tie, it naturally compares the rest of the string, which is the original word.

Limitations (or Trade-offs):

- However, adding to the final array is unnecessarily wordy. It calls get(i) twice, while arr.get(i).substring(1) could've been enough.

- Moreover, re-initializing answer as new String[arr.size()]; is a two-step initialization anti-pattern. Declaring as {} only to immediately overwrite it serves no purpose and signals unclear intent

 

---

Lessons Learned

 

Good code is like a well-written article.
Every word should serve its purpose - not a single word is there without a cause.
As a whole it's like a template - so others can make variations out of it in different occasions.

 

My Github Repository for Solution Code

https://github.com/ginsengcandy/Coding-Test-Practice

GitHub - ginsengcandy/Coding-Test-Practice: This is an auto push repository for Baekjoon Online Judge created with [BaekjoonHub]

Problem Source

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

프로그래머스

 

 

References

About Comparator methods and their applications

https://hianna.tistory.com/922

[Java 기초] Arrays.sort()로 배열 정렬하기

More about Comparator methods

https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html

Comparator (Java Platform SE 8 )

About time complexity comparison beween Arrays.sort() and Collections.sort()

https://yuja-kong.tistory.com/183

[Java] Arrays.sort()와 Collections.sort()의 시간복잡도 비교