C# - O(n) time and O(n) space - simple 2 pointer


  • 0

    initialize a string array with the numbers 1 thru n. Use a right pointer at the end of the array and left pointer at the beginning of the array. Make the array value at the left pointer equal to the combination of the right and left. Keep working inward until the left and right cross, then reset left to 0 and repeat until finally right is also 0 and you're done.

        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];
        }
    

  • 1

    I don't think it's O(n) time but only O(n log n). You first build n strings of "length" 1 (meaning one team), costing n time. Then you build n/2 strings of length 2, costing (n/2)*2 = n time. Then you build n/4 strings of length 4, costing (n/4)*4 = n time. And so on. Each round costs n time, and you have log(n) rounds.


  • 1

    @StefanPochmann thanks for your analysis, this is very interesting, please help me understand this further. The way I was looking at it is the "right" pointer continuously advances from the end to the beginning and thus "n" operations. But you correctly point out that each operation is combining strings that double in length for each "round".

    So, my question is does it cost more to combine longer strings? At first thought, surely it costs more, but I believe this will depend on the implementation. If the strings are linked lists it would be constant time to combine them regardless of the length. Here I am not using linked lists, rather just default string concatenation. Thanks for your explanation!


Log in to reply
 

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