【Video】Using remainder with 3 solutions
Intuition\nUsing remainder\n\n---\n\n# Solution Video\n\nhttps://youtu.be/fDRPdN0dlcs\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! 
# Intuition\nUsing remainder\n\n---\n\n# Solution Video\n\nhttps://youtu.be/fDRPdN0dlcs\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 6,902\nThank you for your support!\n\n---\n\nThis question requires `in-place`, but I think it\'s good idea to have multiple solution for real interviews. Let me share 3 ways. Solution 3 meets `in-place` and $$O(1)$$ space.\n\n# Solution 1\n\n```\nInput: nums = [1,2,3,4,5,6,7], k = 3\n```\nIn this case, we rotate all numbers 3 times. In the end,\n```\n[1,2,3,4,5,6,7]\n\u2193\n[5,6,7,1,2,3,4]\n```\nWhat if `k = 9`?\n```\n[1,2,3,4,5,6,7]\n\u2193\n[6,7,1,2,3,4,5]\n```\n\nDo you have any idea to caluclate rotated position?\n\n---\n\n\u2B50\uFE0F Points\n\nMy idea is to use remainder. \n\n```\nk = k % length of input array\n```\n\nFor instance,\n\n```\n3 % 7 = 3\n9 % 7 = 2\n```\n\nAll we have to do is to rotate all numbers the remainder times.\n\nIf `k = 3`, remainder is `3`.\n\n```\n[1,2,3,4,5,6,7]\n\u2193\n[5,6,7,1,2,3,4]\n```\n\nIf `k = 9`, remainder is `2`.\n```\n[1,2,3,4,5,6,7]\n\u2193\n[6,7,1,2,3,4,5]\n```\n---\n\nWe calculate rotated position with \n```\n(current position + remainder) % length of input array\n```\nFor example, If `k = 9`, rotated position should be\n\n```\nFor 1(= index 0), (0 + 2) % 7 = 2\nFor 2(= index 1), (1 + 2) % 7 = 3\nFor 6(= index 5), (5 + 2) % 7 = 0\nFor 7(= index 6), (6 + 2) % 7 = 1\n```\n\nLet\'s see solution codes!\n\n---\n\nhttps://youtu.be/bU_dXCOWHls\n\n---\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n```python []\nclass Solution:\n    def rotate(self, nums: List[int], k: int) -> None:\n        n = len(nums)\n        k = k % n\n        rotated = [0] * n\n\n        for i in range(n):\n            rotated[(i + k) % n] = nums[i]\n        \n        for i in range(n):\n            nums[i] = rotated[i]\n```\n```javascript []\nvar rotate = function(nums, k) {\n    const n = nums.length;\n    k = k % n;\n    const rotated = new Array(n).fill(0);\n\n    for (let i = 0; i < n; i++) {\n        rotated[(i + k) % n] = nums[i];\n    }\n\n    for (let i = 0; i < n; i++) {\n        nums[i] = rotated[i];\n    }    \n};\n```\n```java []\nclass Solution {\n    public void rotate(int[] nums, int k) {\n        int n = nums.length;\n        k = k % n;\n        int[] rotated = new int[n];\n\n        for (int i = 0; i < n; i++) {\n            rotated[(i + k) % n] = nums[i];\n        }\n\n        for (int i = 0; i < n; i++) {\n            nums[i] = rotated[i];\n        }        \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    void rotate(vector<int>& nums, int k) {\n        int n = nums.size();\n        k = k % n;\n        vector<int> rotated(n);\n\n        for (int i = 0; i < n; i++) {\n            rotated[(i + k) % n] = nums[i];\n        }\n\n        for (int i = 0; i < n; i++) {\n            nums[i] = rotated[i];\n        }        \n    }\n};\n```\n\n# Step by Step Algorithm\n\n1. **Initialization**:\n   - `n` is assigned the length of the array `nums`.\n   - `k` is updated to `k % n` to handle cases where `k` is greater than `n`.\n   ```python\n   n = len(nums)\n   k = k % n\n   ```\n\n2. **Create a New Array for Rotation**:\n   - `rotated` is initialized as a new array of length `n` filled with zeros.\n   ```python\n   rotated = [0] * n\n   ```\n\n3. **Populate the Rotated Array**:\n   - Loop through each element in the original array `nums`.\n   - For each element at index `i`, place it in the `rotated` array at index `(i + k) % n`.\n   ```python\n   for i in range(n):\n       rotated[(i + k) % n] = nums[i]\n   ```\n\n4. **Copy the Rotated Array Back to the Original Array**:\n   - Loop through each element in the `rotated` array.\n   - Copy each element back to the original array `nums`.\n   ```python\n   for i in range(n):\n       nums[i] = rotated[i]\n   ```\n\n---\n\n# Solution 2\n\nWe use remainder again.\n```\nInput: nums = [1,2,3,4,5,6,7], k = 9\n```\nWe create two groups with rotated input array.\n\n---\n\n\u2B50\uFE0F Points\n\nCreate two groups before `k` and after `k`. `k` is remainder, so it\'s `2`, not `9`.\n\n```\n[1,2,3,4,5,6,7]\n\u2193\n[6,7,1,2,3,4,5] (= rotated array)\n\n     k\n[6,7,1,2,3,4,5]\n # # * * * * *\n\n```\nLet\'s think about where # group is coming and * is coming.\n```\n * * * * * # #\n[1,2,3,4,5,6,7]\n```\nLet\'s get together.\n```\n * * * * * # #\n[1,2,3,4,5,6,7]\n[6,7,1,2,3,4,5]\n # # * * * * *\n     k\n```\nAll we have to do is just to swap the same group.\n\n---\n\n\u25FD\uFE0F Question\n\nHow can we express each group?\n\n```\n[6,7,1,2,3,4,5]\n # # * * * * *\n     k\n\nFor #, nums[:k]\nFor *, nums[k:]\n```\n```\n * * * * * # #\n[1,2,3,4,5,6,7]\n\nFor #, nums[-k:]\nFor *, nums[:-k]\n```\n\nsolution should be\n```\nnums[:k], nums[k:] = nums[-k:], nums[:-k]\n```\n\nLet\'s see solution codes!\n\n---\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n```python []\nclass Solution:\n    def rotate(self, nums: List[int], k: int) -> None:\n        k = k % len(nums)\n        if k != 0:\n            nums[:k], nums[k:] = nums[-k:], nums[:-k]\n```\n```javascript []\nvar rotate = function(nums, k) {\n    k = k % nums.length;\n    if (k !== 0) {\n        let temp = nums.slice(-k).concat(nums.slice(0, -k));\n        for (let i = 0; i < nums.length; i++) {\n            nums[i] = temp[i];\n        }\n    }    \n};\n```\n```java []\nclass Solution {\n    public void rotate(int[] nums, int k) {\n        k = k % nums.length;\n        if (k != 0) {\n            int[] temp = new int[nums.length];\n            System.arraycopy(nums, nums.length - k, temp, 0, k);\n            System.arraycopy(nums, 0, temp, k, nums.length - k);\n            System.arraycopy(temp, 0, nums, 0, nums.length);\n        }\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    void rotate(vector<int>& nums, int k) {\n        int n = nums.size();\n        k = k % n;\n        if (k != 0) {\n            vector<int> temp(nums.end() - k, nums.end());\n            temp.insert(temp.end(), nums.begin(), nums.end() - k);\n            copy(temp.begin(), temp.end(), nums.begin());\n        }        \n    }\n};\n```\n\n# Step by Step Algorithm\n\n1. **Calculate Effective Rotations**:\n   - The array\'s length is `n = len(nums)`.\n   - The number of rotations `k` is updated to `k % n` to handle cases where `k` is greater than `n`. This ensures that rotating the array `n` times results in the same array, so any extra rotations beyond `n` can be ignored.\n   ```python\n   k = k % len(nums)\n   ```\n\n2. **Check if Rotation is Needed**:\n   - If `k` is `0`, the array does not need to be rotated, and the function can exit early. This is an optimization step to avoid unnecessary operations.\n   ```python\n   if k != 0:\n   ```\n\n3. **Perform the Rotation**:\n   - If `k` is not `0`, proceed to rotate the array.\n   - The rotation is performed in two parts:\n     - `nums[:k]` will hold the last `k` elements of the original array.\n     - `nums[k:]` will hold the first `n-k` elements of the original array.\n   - Using slicing, the array is reassembled such that the last `k` elements come first, followed by the first `n-k` elements.\n   ```python\n   nums[:k], nums[k:] = nums[-k:], nums[:-k]\n   ```\n\n---\n\n# Solution 3\n\nAgain, we use remainder.\n```\nInput: nums = [1,2,3,4,5,6,7], k = 9\n```\nTo explain the algorithm first, it performs three reverse operations.\n\nFirst of all, we reverse all numbers.\n```\n[1,2,3,4,5,6,7]\n\u2193\n[7,6,5,4,3,2,1]\n```\nThen, we create two groups like solution 2. `Before k` and `After k`.\n```\n     k\n[7,6,5,4,3,2,1]\n # # * * * * *\n\nk is remainder\n```\nThen, reverse all numbers in each group.\n```\n     k\n[7,6,5,4,3,2,1]\n # # * * * * *\n\u2193\n     k\n[6,7,1,2,3,4,5]\n # # * * * * *\n```\n`[6,7,1,2,3,4,5]` is actually answer.\n\nTo summarize the algorithm, we use 3 reverse operation.\n\n```\nreverse(0, last index) \u2192 whole array\nreverse(0, k - 1) \u2192 before k\nreverse(k, last index) \u2192 after k\n```\n\nLet\'s see solution codes!\n\n\n---\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n```python []\nclass Solution:\n    def rotate(self, nums: List[int], k: int) -> None:\n        k %= len(nums)\n\n        def reverse(left, right):\n            while left < right:\n                nums[left], nums[right] = nums[right], nums[left]\n                left += 1\n                right -= 1\n\n        reverse(0, len(nums) - 1)\n        reverse(0, k - 1)\n        reverse(k, len(nums) - 1)\n```\n```javascript []\nvar rotate = function(nums, k) {\n    k %= nums.length;\n\n    const reverse = (left, right) => {\n        while (left < right) {\n            [nums[left], nums[right]] = [nums[right], nums[left]];\n            left++;\n            right--;\n        }\n    };\n\n    reverse(0, nums.length - 1);\n    reverse(0, k - 1);\n    reverse(k, nums.length - 1);    \n};\n```\n```java []\nclass Solution {\n    public void rotate(int[] nums, int k) {\n        k %= nums.length;\n\n        reverse(nums, 0, nums.length - 1);\n        reverse(nums, 0, k - 1);\n        reverse(nums, k, nums.length - 1);\n    }\n\n    private void reverse(int[] nums, int left, int right) {\n        while (left < right) {\n            int temp = nums[left];\n            nums[left] = nums[right];\n            nums[right] = temp;\n            left++;\n            right--;\n        }\n    }    \n}\n```\n```C++ []\nclass Solution {\npublic:\n    void rotate(vector<int>& nums, int k) {\n        k %= nums.size();\n\n        reverse(nums, 0, nums.size() - 1);\n        reverse(nums, 0, k - 1);\n        reverse(nums, k, nums.size() - 1);\n    }\n\nprivate:\n    void reverse(vector<int>& nums, int left, int right) {\n        while (left < right) {\n            swap(nums[left], nums[right]);\n            left++;\n            right--;\n        }\n    }    \n};\n```\n\n# Step by Step Algorithm\n\n1. **Calculate Effective Rotations**:\n   - The length of the array is `n = len(nums)`.\n   - The number of rotations `k` is updated to `k % n` to handle cases where `k` is greater than `n`. This ensures that rotating the array `n` times results in the same array, so any extra rotations beyond `n` can be ignored.\n   ```python\n   k %= len(nums)\n   ```\n\n2. **Define the Reverse Function**:\n   - A helper function `reverse` is defined to reverse the elements of the array between indices `left` and `right`.\n   - Within this function, a while loop swaps elements from the start (`left`) and end (`right`) of the specified segment, moving towards the center until `left` is no longer less than `right`.\n   ```python\n   def reverse(left, right):\n       while left < right:\n           nums[left], nums[right] = nums[right], nums[left]\n           left += 1\n           right -= 1\n   ```\n\n3. **Reverse the Entire Array**:\n   - The entire array is reversed from index `0` to `len(nums) - 1`.\n   - This step places the elements that need to be rotated to the front.\n   ```python\n   reverse(0, len(nums) - 1)\n   ```\n\n4. **Reverse the First `k` Elements**:\n   - The first `k` elements of the reversed array are reversed back to their original order.\n   - This places the rotated elements at the start of the array in their correct positions.\n   ```python\n   reverse(0, k - 1)\n   ```\n\n5. **Reverse the Remaining `n-k` Elements**:\n   - The remaining elements from index `k` to `len(nums) - 1` are reversed back to their original order.\n   - This places the rest of the elements in their correct positions.\n   ```python\n   reverse(k, len(nums) - 1)\n   ```\n---\n\nThank you for reading my post. Please upvote it and don\'t forget to subscribe to my channel!\n\n### \u2B50\uFE0F Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n### \u2B50\uFE0F Twitter\nhttps://twitter.com/CodingNinjaAZ\n\n### \u2B50\uFE0F #48 - Rotate Image\n\nhttps://youtu.be/R1xO_Ear-ww\n
['Array', 'Math', 'Two Pointers', 'Sorting', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']