O(n) solution using Stack

  • 0

    We can use stack to keep track of next largest digit and in the worst case stack can contain a maximum of 8 digits because of the constraint on the input, that said, I'd assume we can treat it as constant space.

        public int MaximumSwap(int num) {
            Stack<char> s = new Stack<char>();
            char[] c = num.ToString().ToCharArray();
            // starting from end, push the large digits on to the stack, if a digit occurrs more than once, then push all the instances
            for(int i=c.Length-2;i>=0;i--)
                if(s.Peek() <= c[i])
            for(int i=0;i<c.Length;i++)
                if(s.Peek() == c[i])
                    // find the last index
                    int idx = Array.LastIndexOf(c, s.Peek());
                    // swap
                    char tmpCh = c[i];
                    c[i] = c[idx];
                    c[idx] = tmpCh;
            return Int32.Parse(new string(c));

Log in to reply

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