3 Solutions | Easy, Medium & Hard | Explained
There are 3 methods to solve this question:\n1) Brute-Force Method : \ni. Purely Brute-force, no optimization\nii. a little optimized (but still brute-force)\n(
There are 3 methods to solve this question:\n1) Brute-Force Method : \ni. Purely Brute-force, no optimization\nii. a little optimized (but still brute-force)\n( In either of the cases above Time Limit will exceed )\n\nIn the i. part we will simply rotate for k times (which is given). It is the most basic approach which will come to everyone\'s mind at first thought. \n\nCode for the Above :-\n\n```\nclass Solution {\npublic:\n    void rotate(vector<int>& nums, int k) {\n\n        for(int i = 1; i <= k; i++){\n            //code for simple rotation\n            int temp = nums[0];\n            for(int idx = 1; idx < nums.size(); idx++){\n                int temp1 = nums[idx];\n                nums[idx] = temp;\n                temp = temp1;\n            }\n            nums[0] = temp;\n        }\n    //Note: Time Limit will Exceed\n    }\n};\n```\nNow Let\'s think, do we really need to rotate K times? If we check carefully after rotating for a total of n times (where n is equal to length of the array) we will reach at the initial state of our array. **How?** Let\'s take a look at the below example:\n```\nfor eg, array is = [1, 2, 3]\n Let\'s say we have to rotate the above array for 3 times\n which is equal to the length of the array (say length is n).\n Let\'s rotate,\n    First Rotation: [3, 1, 2]\n    Second Rotation: [2, 3, 1]\n    Third Rotation: [1, 2, 3]\n \n Isn\'t the array we got after n rotations equal to our initial \n array? So actually we did waste 3 iteration for the same task\n which could have been done in 0 iteration, right?\n```\nWhich leads us to our Brute-Force ii. method:\n```\nHere we will only rotate for k % size of array times.\nwhere k is the number of times given to rotate.\n\nLet\'s Rotate the same array of our previous example: [1, 2, 3],\nfor a total of 7 times, i.e, k = 7.\n\nFirst, Let\'s do the same with the help of Brute-Force i. method:\n[using r as abbreviation for rotation]\n1st r: [3, 1, 2]\n2nd r: [2, 3, 1]\n3rd r: [1, 2, 3] -> see how we returned to initial state\n4th r: [3, 1, 2]\n5th r: [2, 3, 1]\n6th r: [1, 2, 3] -> notice we once again reached initial state\n7th r: [3, 1, 2]\n\nLet\'s try rotating with our Brute-Force ii. method:\ntimesToRotate = k % size => 7 % 3 = 1\nRotating timesToRotate times now, i.e, 1 time:\noriginal array: [1, 2, 3]\nafter 1st r: [3, 1, 2]\n\nDidn\'t we get the same array we got by using our first approach?\nAlso we didn\'t have to waste so many iterations with the help of a\nsimple mod operation.\n```\nLet\'s see the Code for the Above Approach:\n```\nclass Solution {\npublic:\n    void rotate(vector<int>& nums, int k) {\n        int timesToRotate = k % nums.size();\n\n        for(int i = 1; i <= timesToRotate; i++){\n            int temp = nums[0];\n            for(int idx = 1; idx < nums.size(); idx++){\n                int temp1 = nums[idx];\n                nums[idx] = temp;\n                temp = temp1;\n            }\n            nums[0] = temp;\n        }\n        //Note: Time Limit will still exceed\n    }\n};\n```\nOkay, very Well, we now know our first approach, but come to think of it, why is the time limit still exceeding? it\'s because we are shifting the elements in the array one-by-one for a total of k times or k % size times with the help of our 1st Approach, which ultimately is a time consuming task even if we optimized it.\nCan we do the same task in O(n) time, i.e, in a single traversal? to do so we have to understand our 2nd Approach:\n2) We now know that we only need to rotate for t times now, lets say t = k % size by our first approach. Now what if we create a second array and directly store the corresponding elements of our main array at the proper location they should be after rotation and then copy it back to our main array. Note: The Time complexity will surely be reduced but we will have to use extra space for another array in this case.\n\nLet\'s understand the above in a little more depth:\n```\nLet\'s Say we have the same array: [1, 2, 3]\nWe also create a temporary array: [0, 0, 0] <- 0 denoting no values\n(which has the same size as the main array but is currently NULL)\n\nLet\'s say k = 7,\ntherefore t = k % size => 7 % 3 = 1\n\nNow, what if we store each element of first array at \n(current index + t) % (size of array) index in our secondary \narray.\n\nFor example:\nin our main array: 1 is at index -> 0\n                   2 is at index -> 1\n                   3 is at index -> 2\n\nSo in our secondary array we should store 1 at:\n    (index of 1 in main array + t) % size => (0 + 1) % 3 = 1\nSo our secondary array becomes: [0, 1, 0]\n\nDoing the same element 2 of main array:\n    (2s index in main array + t) % size => (1 + 1) % 3 = 2\nSecondary array becomes: [0, 1, 2]\n\nDoing the same with element 3 of main array:\n    (3s index in main array + t) % size => (2 + 1) % 3 = 0\nSecondary array becomes: [3, 1, 2]\nNow simply copy it to our main array.\n\nWhy did we have to mod the position to provide in array2 \nby the size? it could have been done without it? Well, \nwe did it to save ourselves from handling the edge cases when\nindex becomes greater than size - 1 of array, which if is not\nhandled will give us ArrayOutOfBounds kind of error.\n\nHere we only traversed the main array once hence Time Complexity \nwill be = O(n),\nand O(n) time will also be taken for copying, making the\nTotal Complexity = O(n) + O(n) = O(n) (in general)\n```\nLet\'s see the Implementation of the above code,\n (This time it won\'t exceed the time limit):\n```\nclass Solution {\npublic:\n    void rotate(vector<int>& nums, int k) {\n        int timesToRotate = k % nums.size();\n\n        vector<int> temp(nums.size());\n        \n        for(int i = 0; i < nums.size(); i++)\n            temp[(i + timesToRotate) % nums.size()] = nums[i];\n        \n        //copying the array\n        for(int i = 0; i < nums.size(); i++)\n            nums[i] = temp[i];\n    }\n};\n```\nNow, we have done the task in O(n) time, so why do we need more approaches? The reason being we took extra space in our last approach, Can we do the same task in O(n) time without using extra space? the answer is Yes we can, which brings us our 3rd Approach:\n\n3) Now this approach TBH is tricky and you won\'t understand it unless you dry run it, and for your curiousity neither was I able to understand it without implementing.\nIn this approach we will :\n    First: Reverse the whole array.\n    Second: Reverse from starting till t - 1 index (where t = k % length/size of array).\n    Third: Reverse from index t till the last index of the array.\n\nDidn\'t understand any of the above? Worry not, let\'s understand in a little depth:\n```\nLet\'s take our favourite array: [1, 2, 3]\nand our favourite k, which is: 7 times\nour t becomes: k % size of array => 7 % 3 = 1\n\nStep 1: Reverse the whole array:\n    [3, 2, 1]\nStep 2: Reverse from start (which is 0th index) till t-1 index:\n    t = 1\n    t - 1 = 0\n    Reverse from 0 to 0th index, which is basically doing nothing\n    [3, 2, 1]\nStep 3: Reverse from index t to end of array:\n    t = 1\n    last index = size - 1 => 3 - 1 = 2\n    reversing from index 1 to 2:\n    [3, 1, 2] <- Isn\'t this the very array we were asked to fetch?\n\nSo here we solved the question without using any extra space like\nour 2nd approach.\n```\nNow, I have written the code in cpp which has a function which takes the parameter of both the start point of the reverse and the end point of the reverse (where the end point is not included). If you use some other language you might have to create a function to reverse which accepts both starting and ending points seperately (which is pretty easy to do) or pass your parameters of indexes a little differently than me. However, the logic remains the same as above.\n\nMy Cpp code for the same:\n```\nclass Solution {\npublic:\n    void rotate(vector<int>& nums, int k) {\n        int timesToRotate = k % nums.size();\n\n        reverse(nums.begin(), nums.end());\n        reverse(nums.begin(), nums.begin() + timesToRotate);\n        reverse(nums.begin() + timesToRotate, nums.end());\n\n    }\n};\n```\n> **If you read till here and found it helpful then don\'t forget to UP VOTE**
['Array', 'Math', 'C', 'C++', 'Java']