Smallest self distances
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nIt is not a complicated problem but take quite some experiments to find out what 
![Screenshot 2024-02-24 at 7.33.12\u202FPM.png](https://assets.leetcode.com/users/images/1ba26bb2-1d65-40cb-ba54-b67be638ba56_1708832036.531272.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt is not a complicated problem but take quite some experiments to find out what this problem is about - maximum self distance of any value to same value, i.e. number of different values between two occurrences circularly. For example, in [1,2,2,1], the value 1 at index 0 and index 3 has two other numbers between them. Similarly the value 2 at index 1 and index 2 has two other numbers between them circularly. In [1,2,3,1,2,3,1]. There are two different numbers between value at index 0 and index 3, index 3 and index 6. Since every second we can change a value both way, so it will take about dist/2 + dist%2 seconds to change all other numbers the any value. We need to find the value that has the smallest maximum self distance.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFor every distinct value, get its index ranges in the input. So it will be easy to calculate max distance for any distinctive value. Then we could get the minimum once all distinctive values are considered. This will be the answer we are looking for this problem.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n) where n is size of input array.\nPlease note that even in our code there is a nested loop, however, all ranges of distinctive values add up at most to n. So total calculations add up to O(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n) where n is size of input array.\nA dictionary is used to keep all ranges of distinctive values for easier calculation of max distances.\n\n# Code\n```\nclass Solution {\n    func minimumSeconds(_ nums: [Int]) -> Int {\n        guard nums.count > 1 else {return 0}\n        return mxDist(nums)\n    }\n\n    func mxDist(_ nums: [Int]) -> Int {\n        let N = nums.count\n        var a: [Int:[[Int]]] = [:]\n        var i = 0\n        while i < N {\n            let n = nums[i]\n            var j = i + 1\n            while j < N && nums[j] == n {\n                j += 1\n            }\n            a[n, default: []].append([i, j-1]) //inclusive\n            i = j\n        }\n        if a.count == 1 {return 0}\n        var mx = N\n        for (n, ranges) in a {\n            //find out max dist in ranges\n            var d = 0\n            if ranges.count == 1 {\n                let others = N - (ranges[0][1] - ranges[0][0] + 1)\n                d = others/2 + others%2\n            } else {\n                var others = 0\n                var i = 1\n                while i < ranges.count {\n                    others = max(ranges[i][0] - 1 - ranges[i-1][1], others)\n                    i += 1\n                }\n                others = max(others, N - 1 - ranges.last![1] + ranges.first![0])\n                d = others/2 + others%2\n            }\n            mx = min(mx, d)\n        }\n        return mx\n    }\n}\n```
['Swift']