O(n) solution using Stack


  • 0
    P

    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
            s.Push(c[c.Length-1]);
            for(int i=c.Length-2;i>=0;i--)
            {
                if(s.Peek() <= c[i])
                {
                    s.Push(c[i]);
                }
            }
            
            for(int i=0;i<c.Length;i++)
            {
                if(s.Peek() == c[i])
                {
                    s.Pop();
                }
                else
                {
                    // find the last index
                    int idx = Array.LastIndexOf(c, s.Peek());
                    // swap
                    char tmpCh = c[i];
                    c[i] = c[idx];
                    c[idx] = tmpCh;
                    break;
                }
            }
            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.