[C++] 2 Pointer Solution, 7ms, 46.3MB
For this problem we have to just find the indexes of 1 and the value matching length of nums, then check how far they are from being in the first and in the las
For this problem we have to just find the indexes of `1` and the value matching length of `nums`, then check how far they are from being in the first and in the last position - with a caveat: if the first position is `>` than the last one, when we start swapping one of the indexes we will put the latter closer to its position, so we need to take that into account.\n\nNow, to code our solution, let\'s start with declaring our support variables:\n* `len` will store the length of `nums`;\n* `p1` and `p2` will be where we store the positions of the values `1` and `len` respectively, both initially set to be `-1`.\n\nWe will then loop with `i` across all the positions in `nums` until we have found both pointers (ie: `p1 == -1 || p2 == -1`) and:\n* store `nums[i]` in `n`;\n* if `n == 1`, we will set `p1` to be `i`;\n* otherwise, if `n == len`, we will set `p2` to be `i`.\n\nOnce done, we will `return` the sum of the distances of `p1` from the first position (ie: `p1 - 0`) and `p2` from the last position (ie: `len - p2 - 1`), adjusted by `-1` as we mentioned in our incipit if `p1 > p2`.\n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(1)$$\n\n# Code\n```cpp\nclass Solution {\npublic:\n    int semiOrderedPermutation(vector<int> &nums) {\n        // support variables\n        int len = nums.size(), p1 = -1, p2 = -1;\n        // parsing nums\n        for (int i = 0, n; p1 == -1 || p2 == -1; i++) {\n            n = nums[i];\n            if (n == 1) p1 = i;\n            else if (n == len) p2 = i;\n        }\n        return (p1 > p2 ? -1 : 0) + p1 + len - p2 - 1;\n    }\n};\n```\n\nAlternative version of that logic, working directly with a variable result `res` and a boolean flag `foundOne` to check if we had already found the other index before. Notice that now we need to do one less check at each loop iteration and that we use `foundOne` in the `else if` clause to decrease the value of `res` by `1` if we had found `1` before `len`; overall, this version seemed to perform a bit better:\n\n```cpp\nclass Solution {\npublic:\n    int semiOrderedPermutation(vector<int> &nums) {\n        // support variables\n        int len = nums.size(), res = 0;\n        bool foundOne = false;\n        // parsing nums\n        for (int i = 0, n; ; i++) {\n            n = nums[i];\n            if (n == 1) {\n                res += i;\n                if (foundOne) break;\n                foundOne = true;\n            }\n            else if (n == len) {\n                res += len - i - 1 - !foundOne;\n                if (foundOne) break;\n                foundOne = true;\n            }\n        }\n        return res;\n    }\n};\n```
['Array', 'Two Pointers', 'C++']