JAVA iterative O(NlgN) Two Pointer Solution; 12ms


  • 0
    H

    public String findContestMatch(int n) {

        //Algo thinking: Two pointers
        
        // time = O(N + N/2 + N/4 + ... + 1) = O(NlgN), space = O(N)
        
        
        List<String> match = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            match.add(i + "");
        }
        
        while (match.size() > 1) {
            List<String> nextMatch = new ArrayList<>();
            int head = 0, tail = match.size() - 1;
            while (head < tail) {
                nextMatch.add("(" + match.get(head++) + "," + match.get(tail--) + ")");
            }
            match = nextMatch;
        }
        
        return match.get(0);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.