public class Solution {
public String findContestMatch(int n) {
List<String> matches = new ArrayList<>();
for(int i = 1; i <= n; i++) matches.add(String.valueOf(i));
while(matches.size() != 1){
List<String> newRound = new ArrayList<>();
for(int i = 0; i < matches.size()/2; i++)
newRound.add("(" + matches.get(i) + "," + matches.get(matches.size()  i  1) + ")");
matches = newRound;
}
return matches.get(0);
}
}
Java 10 lines


Same idea. Indeed, we can even do this in an inplace fashion.
public String findContestMatch(int n) { String[] res = new String[n]; for (int i = 1; i <= n; i++) res[i  1] = "" + i; for (; n > 1; n /= 2) for (int i = 0; i < n / 2; i++) res[i] = "(" + res[i] + "," + res[n  1  i] + ")"; return res[0]; }
Furthermore, if one uses a LinkedList to implement the string, the code can run in
O(n)
time.
Update: The (long) implementation is shown as follows, which uses theListNode
that is predefined by LeetCode.private ListNode[] intToList(int n) { ListNode head = null, tail = null; if (n == 0) head = tail = new ListNode('0'); else { while (n > 0) { ListNode p = new ListNode(n % 10 + '0'); p.next = head; head = p; n /= 10; if (tail == null) tail = head; } } return new ListNode[]{head, tail}; } public String findContestMatch(int n) { ListNode[] heads = new ListNode[n]; ListNode[] tails = new ListNode[n]; for (int i = 0; i < n; i++) { ListNode[] list = intToList(i + 1); heads[i] = list[0]; tails[i] = list[1]; } for (; n > 1; n /= 2) for (int i = 0; i < n / 2; i++) { ListNode leftParen = new ListNode('('); ListNode comma = new ListNode(','); ListNode rightParen = new ListNode(')'); leftParen.next = heads[i]; tails[i].next = comma; comma.next = heads[n  1  i]; tails[n  1  i].next = rightParen; heads[i] = leftParen; tails[i] = rightParen; } StringBuilder builder = new StringBuilder(); for (ListNode p = heads[0]; p != null; p = p.next) builder.append((char) p.val); return builder.toString(); }

@lixx2100 same here, in place as well, using 2 pointer instead of for loops.
public string FindContestMatch(int n) { string[] arr = new string[n]; for (int i = 0; i < n; i++) arr[i] = (i + 1).ToString(); int left = 0; int right = n  1; while (left < right) { while (left < right) { arr[left] = "(" + arr[left] + "," + arr[right] + ")"; left++; right; } left = 0; } return arr[0]; }

@whglamrock If we assume string concatenation takes
O(1)
time, the above code runs inO(n)
time, since the runtime is the sum of the geometric sequencen/2, n/4, ..., 4, 2, 1
.Now, if we store each number in a doubly linked list node, string concatenation is just like merging two linked lists, which can be done in
O(1)
time. There aren
numbers in total, and at most3n
extra nodes will be created, for those(
,,
,)
, resulting a total runtime/space ofO(4n) = O(n)
.

@lixx2100 correct me if I am wrong
At first, n/2 + n/4 + ... + 4 + 2 + 1 is O(logN) time, not O(N).
Second, I don't know how you jump to the conclusion that one number only needs one "(", one ")" and one ",". If you could give logical deduction I would really appreciate.
Third, the string concatenation surely takes O(N) because we need to recreate a new string. In terms of using doublylinked list, you need to justify the above point ("3 extra" nodes for each number), otherwise you cannot guarantee how many "(" or ")" you need to put on each side of the number.

@whglamrock First,
n/2 + n/4 + ... + 4 + 2 + 1 = O(n)
. Even the first termn/2
is significantly greater thanO(log n)
. Whenn
is a power of 2,n/2 + n/4 + ... + 4 + 2 + 1 = n  1
.Regarding your second and third question, I will write an implementation later today. And I guess the code would be better selfexplanatory.
Update: I had an implementation in my original post, which runs in
O(n)
time. String concatenations there are "achieved" by linked list concatenations, which takeO(1)
time.

Sorry I didn't make it clear...
Everybody knows how to calculate n/2 + n/4 + n/8 + ... + 4 + 2 + 1 since it is a simple geometric sequence. I was saying it has O(logN) items whereas the number of items decides the number of loops (in your linkedlist case, the concatenation of nodes).
However, if you can prove that each number needs exactly three extra chars, then we can ignore, jump out of the above discussion because what matters then will be the total number of operations, which is the sum of (n/2 + n/4 + n/8 + ... + 4 + 2 + 1).

@whglamrock Just observe the number of
(
,,
,)
in the final output is also equal ton/2 + n/4 + ... + 4 + 2 + 1 = n  1
. Therefore, in total we have exactly3n  3
extra characters.
If you like, you can say, in an average case, each number requires no more than 3 chars.

Recursion use Deque.
public String findContestMatch(int n) { Deque<String> deque = new ArrayDeque(); for(int i = 1; i <= n; i++){ deque.addLast(String.valueOf(i)); } return helper(deque); } String helper(Deque<String> deque){ if(deque.size() == 1) return deque.pollFirst(); Deque<String> newDeque = new ArrayDeque(); while(!deque.isEmpty()){ newDeque.addLast("(" + deque.pollFirst() + "," + deque.pollLast() + ")"); } return helper(newDeque); }

Iterative version.
public class Solution { public String findContestMatch(int n) { Deque<String> queue = new ArrayDeque<>(); for (int i = 1; i <= n; i++) { queue.offer(String.valueOf(i)); } while (queue.size() > 1) { Deque<String> nextQueue = new ArrayDeque<>(); while (!queue.isEmpty()) { nextQueue.offer("(" + queue.poll() + "," + queue.pollLast() + ")"); } queue = nextQueue; } return queue.poll(); } }