Swift O(n) time solution


  • 0
    L

    Turn the number to a list of digits. Traverse backwards, for each digit d, if d is smaller than the maximum M of all digits behind it, then d may be swapped with M to obtain a larger number.

    The idea is that the last (d, M) pair found is the pair to swap.
    It may be explained as a greedy approach.

    Update indices of (d, M) when such pair is found. Check that index of d is strictly less than that of M. Finally swap digits if valid.

    class Solution {
        func maximumSwap(_ num: Int) -> Int {
            var M = -1
            let s = String(num)
            var L = s.characters.count 
            var R = -1
            var curM = -1
            var nums = s.characters.map {
                Int(String($0))!
            }
            for (i, d) in nums.enumerated().reversed() {
                if d < M {
                    L = i
                    R = curM
                }
                else if d > M {
                    M = d
                    curM = i
                }
            }
            guard L < nums.count && R > -1 else {
                return num
            }
            let t = nums[L]
            nums[L] = nums[R]
            nums[R] = t
            return Int(nums.map{String($0)}.joined(separator: ""))!
        }
    }
    

Log in to reply
 

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