Python_100DaysofCode/RotateArrayDay5.py at main · ayushlingayat/Python_100DaysofCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#Brute Force

# class Solution:
    # def rotate(self, nums, k):
    #     n = len(nums)
    #     k = k % n  # In case k > n
    #
    #     for _ in range(k):
    #         last = nums[-1]
    #         for i in range(n - 1, 0, -1):
    #             nums[i] = nums[i - 1]
    #         nums[0] = last

#
# Time Complexity: O(n * k)
# Space Complexity: O(1) (in-place)


#Better Solution

# class Solution:
#     def rotate(self, nums, k):
#         n = len(nums)
#         k = k % n  # In case k > n
#         temp = [0] * n
#
#         for i in range(n):
#             temp[(i + k) % n] = nums[i]
#
#         for i in range(n):
#             nums[i] = temp[i]

# Time Complexity: O(n)
# Space Complexity: O(n) (using temp array)

#Optimal Approach

class Solution:
    def rotate(self, nums, k):
        n = len(nums)
        k = k % n

        def reverse(start, end):
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1

        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)


# Time Complexity: O(n)
# Space Complexity: O(1) (in-place)