Skip to content

01. Two Pointer

Theory

Description

The Two Pointer Pattern is a technique used to solve problems involving sequences (such as arrays or lists) by utilizing two pointers that traverse the sequence in different ways. This approach is particularly effective in optimizing performance by reducing time complexity, especially for problems that involve checking pairs, subarrays, or sliding windows.

This technique should be your go-to when you see a question that involves searching for a pair (or more!) of elements in an array that meet a certain criteria.

Types

Same Direction

When to Use

  • This technique is ideal for problems like finding unique elements, counting subarrays, or rearranging elements.

How It Works

  • One pointer (typically called slow) moves through the array, while the other pointer (called fast) explores further elements.
  • The slow pointer often keeps track of the current valid position, while the fast pointer scans for new valid elements.
  • This is especially useful for sliding window problems, where the window expands and shrinks by adjusting the pointers.
  • It can also be used to remove duplicates in-place in an array.

1. Sort Array By Parity II (Leetcode:922)

Problem Statement

Given an array of integers nums, half of the integers in nums are odd, and the other half are even.
Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.
Return any answer array that satisfies this condition.

Example 1:

Input: nums = [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Example 2:

Input: nums = [2,3]
Output: [2,3]

Constraints:

2 <= nums.length <= 2 * 10^4
nums.length is even.
Half of the integers in nums are even.
0 <= nums[i] <= 1000

Follow Up:

Could you solve it in-place?

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def sortArrayByParityII(self, nums: List[int]) -> List[int]:
    even, odd = 0, 1
    n = len(nums)

    while even < n and odd < n:
        # If even index has an even number, move to next even index
        if nums[even] % 2 == 0:
            even += 2
        # If odd index has an odd number, move to next odd index
        elif nums[odd] % 2 == 1:
            odd += 2
        else:
            # Swap misplaced values
            nums[even], nums[odd] = nums[odd], nums[even]
            even += 2
            odd += 2

    return nums
Explaination:

  1. Initialization :

    • even = 0, odd = 1: Pointers to track the next even and odd indices respectively.
    • n = len(nums): Stores the total number of elements in nums.

  2. Loop through array :

    • While even < n and odd < n:
      • If the element at the even index is even (nums[even] % 2 == 0), move even to the next even index (even += 2).
      • Else if the element at the odd index is odd (nums[odd] % 2 == 1), move odd to the next odd index (odd += 2).
      • Else: Swap the elements at indices even and odd (nums[even], nums[odd] = nums[odd], nums[even]), then move both pointers forward by 2.

  3. Return result :

    • After the loop, return the rearranged array nums where even indices hold even numbers and odd indices hold odd numbers.

1
2
3
4
5
6
7
8
9
def sortArrayByParityII(nums):
    evens = [x for x in nums if x % 2 == 0]
    odds = [x for x in nums if x % 2 == 1]

    res = [0] * len(nums)
    res[0::2] = evens  # Fill even indices
    res[1::2] = odds   # Fill odd indices

    return res
Explaination:

  1. Initialization :

    • evens = [x for x in nums if x % 2 == 0]: Creates a list of all even numbers from nums.
    • odds = [x for x in nums if x % 2 == 1]: Creates a list of all odd numbers from nums.
    • res = [0] * len(nums): Initializes a result list of the same length as nums filled with zeros.

  2. Fill positions :

    • res[0::2] = evens: Assigns even numbers to even indices of res.
    • res[1::2] = odds: Assigns odd numbers to odd indices of res.

  3. Return result :

    • Return the list res where even indices contain even numbers and odd indices contain odd numbers.

Staged Traversal

When to Use

  • Useful when the traversal involves conditional or nested passes, such as partitioning arrays, in-place rearrangements, or sorting by repeatedly scanning for conditions.

How It Works

  • One pointer iterates through the data sequentially.
  • When a certain condition is met, a second pointer or inner loop activates to perform an action (swap, scan, etc.).
  • This staged, conditional movement allows fine-grained control of elements based on dynamic criteria.

1. Sort Colors (Leetcode:75)

Problem Statement

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
You must solve this problem without using the library's sort function.
Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example 2:
Input: nums = [2,0,1] Output: [0,1,2]

Constraints:

n == nums.length
1 <= n <= 300
nums[i] is either 0, 1, or 2.

Follow Up:
Could you come up with a one-pass algorithm using only constant extra space?

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def sortColors(nums):
    left, right = 0, len(nums) - 1
    i = 0

    while i <= right:
        if nums[i] == 0:
            nums[i], nums[left] = nums[left], nums[i]
            left += 1
            i += 1
        elif nums[i] == 2:
            nums[i], nums[right] = nums[right], nums[i]
            right -= 1
        else:  # nums[i] == 1
            i += 1
Explaination:
This is two pointer approach (partitioning array)

  1. Initialization :

    • left = 0, right = len(nums) - 1: Pointers for the next position of 0 and 2 respectively.
    • i = 0: Current index being processed.

  2. Three-way partition (Dutch National Flag algorithm) :

    • While i <= right:
      • If nums[i] == 0:
        • Swap nums[i] with nums[left] to move 0 to the left side.
        • Increment both left and i.
      • Else if nums[i] == 2:
        • Swap nums[i] with nums[right] to move 2 to the right side.
        • Decrement right (do not increment i because swapped value needs to be checked).
      • Else (nums[i] == 1):
        • Increment i to process the next element.

  3. In-place result :

    • At the end of the loop, the array nums will be sorted with all 0s first, followed by 1s, then 2s. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
Explaination:
This is Dutch National Flag approach

  1. Initialization :

    • low = 0: Pointer to the position where the next 0 should be placed.
    • mid = 0: Pointer to the current element being examined.
    • high = len(nums) - 1: Pointer to the position where the next 2 should be placed.

  2. Loop through array :

    • While mid <= high:
      • If nums[mid] == 0: Swap nums[low] and nums[mid], then increment both low and mid.
      • Else if nums[mid] == 1: Increment mid (correct position, move forward).
      • Else (nums[mid] == 2): Swap nums[mid] and nums[high], then decrement high.

  3. Return result :

    • The list nums is sorted in-place with all 0s first, followed by 1s, then 2s.

2. Largest Number (Leetcode:179)

Problem Statement

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.
Since the result may be very large, so you need to return a string instead of an integer.

Example 1:

Input: nums = [10,2]
Output: "210"

Example 2:

Input: nums = [3,30,34,5,9]
Output: "9534330"

Constraints:

1 <= nums.length <= 100 0 <= nums[i] <= 109

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def largestNumber(self, nums: List[int]) -> str:
    nums_str = list(map(str, nums))

    def compare(a, b):
        return -1 if a + b > b + a else (1 if a + b < b + a else 0)

    nums_str.sort(key=cmp_to_key(compare))
    result = ''.join(nums_str)

    return '0' if result[0] == '0' else result
Explaination:
This is optimal approach

  1. Convert to strings :

    • nums_str = list(map(str, nums)): Converts all integers in nums to strings for concatenation-based comparison.

  2. Custom comparator :

    • compare(a, b):
      • Returns -1 if a + b is greater than b + a (meaning a should come before b).
      • Returns 1 if a + b is less than b + a (meaning b should come before a).
      • Returns 0 if they are equal.

  3. Sort using custom logic :

    • nums_str.sort(key=cmp_to_key(compare)): Sorts the list of string numbers so that their concatenation forms the largest possible number.

  4. Join to form result :

    • result = ''.join(nums_str): Combines all sorted string numbers into a single string.

  5. Handle leading zeros :

    • If the first character of result is '0', return '0' (covers the case where all numbers are zeros).
    • Otherwise, return result.

  6. Result :

    • Returns the largest number possible by arranging the integers in nums.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def largestNumber(self, nums: List[int]) -> str:
    nums_str = list(map(str, nums))
    n = len(nums_str)

    # Bubble sort using two pointers
    for i in range(n):
        for j in range(i + 1, n):
            if nums_str[i] + nums_str[j] < nums_str[j] + nums_str[i]:
                nums_str[i], nums_str[j] = nums_str[j], nums_str[i]

    result = ''.join(nums_str)
    return '0' if result[0] == '0' else result
Explaination:
This is bubble-sort approach

  1. Initialization:

    • nums_str = list(map(str, nums)): Converts all numbers in the input list nums to strings to facilitate concatenation and comparison.
    • n = len(nums_str): Stores the length of the input list.

  2. Bubble Sort using Two Pointers:

    • The algorithm uses nested loops (for i in range(n) and for j in range(i + 1, n)) to compare every possible pair of numbers.
    • For each pair (i, j):
      • Custom Comparison:
        If nums_str[i] + nums_str[j] < nums_str[j] + nums_str[i], their order is swapped.
      • This ensures that the concatenation of the numbers forms the largest possible number when joined.
      • Example:
        If comparing '3' and '30':
      • '3' + '30' = '330'
      • '30' + '3' = '303'
      • Since '330' > '303', '3' should come before '30'.

  3. Result Construction:

    • ''.join(nums_str): Concatenates the sorted strings into the final number.
    • return '0' if result[0] == '0' else result:
      • If the first digit is '0', it means all numbers are zeros, so return '0'.
      • Otherwise, return the concatenated result.

3. First Missing Positive (Leetcode:41)

Problem Statement

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space. Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def firstMissingPositive(self, nums: List[int]) -> int:
    n = len(nums)

    # Place each number at the correct index
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

    # Find the first missing positive
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    return n + 1
Explaination:
This is first approach

Opposite End

When to Use

  • This technique is ideal for problems where you need to find pairs that satisfy a specific condition, such as a target sum or product, especially in sorted arrays.

How It Works

  • One pointer starts at the beginning of the array (left pointer), and the other starts at the end (right pointer).
  • Both pointers move towards each other, adjusting based on the condition being checked.
  • If the sum of the values at both pointers meets the condition (e.g., equals a target sum), return the result.
  • If the sum is too low, move the left pointer forward; if it's too high, move the right pointer backward.
  • This method is efficient for problems like "two-sum" or "pair sum" problems in sorted arrays.

1. Two Sum (Leetcode:1)

Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.
Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 10^4 -10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Only one valid answer exists.

Follow Up:

Can you come up with an algorithm that is less than O(n^2) time complexity?

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from typing import List

def two_sum(nums: List[int], target: int) -> List[int]:
    # Step 1: Pair values with original indices
    paired = [(num, i) for i, num in enumerate(nums)]

    # Step 2: Sort by the numbers
    paired.sort(key=lambda x: x[0])

    # Step 3: Use two pointers
    left, right = 0, len(paired) - 1
    while left < right:
        current_sum = paired[left][0] + paired[right][0]
        if current_sum == target:
            # Step 4: Return the original indices
            return [paired[left][1], paired[right][1]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    # By problem constraints, this line should never be reached
    raise ValueError("No two sum solution found")
Explaination:
This is using two pointers approach

  1. Pair values with indices :

    • paired = [(num, i) for i, num in enumerate(nums)]: Creates a list of tuples containing each number and its original index.

  2. Sort pairs by value :

    • paired.sort(key=lambda x: x[0]): Sorts the list of pairs based on the number (first element of each tuple).

  3. Two-pointer search :

    • Initialize left = 0 and right = len(paired) - 1.
    • While left < right:
      • Calculate current_sum = paired[left][0] + paired[right][0].
      • If current_sum == target: Return the original indices [paired[left][1], paired[right][1]].
      • If current_sum < target: Move left pointer right (left += 1) to increase the sum.
      • Else: Move right pointer left (right -= 1) to decrease the sum.

  4. Error handling :

    • If no pair is found (should not happen by constraints), raise a ValueError. 

1
2
3
4
5
6
7
def twoSum(nums, target):
    num_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i
Explaination:
This is optimal approach

  1. Initialization :

    • num_map = {}: A dictionary to store numbers as keys and their indices as values for quick lookups.

  2. Loop through nums :

    • For each index i and value num:
      • Calculate complement = target - num.
      • If complement exists in num_map:
        • Return [num_map[complement], i], which are the indices of the two numbers that sum to the target.
      • Otherwise, store the current number and its index in num_map (num_map[num] = i).

  3. Return result :

    • The function returns as soon as a valid pair is found, ensuring O(n) time complexity.

2: Container With Most Water(Leetcode:11)

Problem Statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

Constraints:

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0

    while left < right:
        h = min(height[left], height[right])
        w = right - left
        max_area = max(max_area, h * w)

        # Move the shorter pointer inward
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area
Explaination:
This is both two pointer and greedy approach

  1. Initialization :

    • left = 0, right = len(height) - 1: Two pointers at the start and end of the list.
    • max_area = 0: Tracks the maximum container area found so far.

  2. Two-pointer loop :

    • While left < right:
      • h = min(height[left], height[right]): Height is determined by the shorter line.
      • w = right - left: Width is the distance between the two pointers.
      • Update max_area = max(max_area, h * w) to store the largest area found.

  3. Pointer movement :

    • If height[left] < height[right]: Move left pointer right (left += 1) to try finding a taller line.
    • Else: Move right pointer left (right -= 1) for the same reason.

  4. Return result :

    • Return max_area, the largest possible water container area.

3: Valid Triangle Number(Leetcode:611)

Problem Statement

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Example 2:

Input: nums = [4,2,3,4]
Output: 4

Constraints:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def triangleNumber(nums):
    nums.sort()

    count = 0
    for i in range(len(nums) - 1, 1, -1):
        left = 0
        right = i - 1
        while left < right:
            if nums[left] + nums[right] > nums[i]:
                count += right - left
                right -= 1
            else:
                left += 1

    return count
Explaination:

  1. Sort the array :

    • nums.sort(): Sorts the list in non-decreasing order to simplify the triangle inequality check.

  2. Initialize counter :

    • count = 0: Tracks the number of valid triangles.

  3. Fix the largest side :

    • Loop i from len(nums) - 1 down to 2:
      • Treat nums[i] as the largest side of the triangle.

  4. Two-pointer search for other sides :

    • Set left = 0 and right = i - 1.
    • While left < right:
      • If nums[left] + nums[right] > nums[i]:
        • All pairs from left to right-1 with right are valid (since the array is sorted).
        • Increment count by right - left.
        • Move right pointer left (right -= 1).
      • Else: Move left pointer right (left += 1) to increase the sum.

  5. Return result :

    • Return count, the total number of valid triangles possible.

4. DI String Match (Leetcode:942)

Problem Statement

A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:

s[i] == 'I' if perm[i] < perm[i + 1], and
s[i] == 'D' if perm[i] > perm[i + 1].

Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.

Example 1:

Input: s = "IDID"
Output: [0,4,1,3,2]

Example 2:

Input: s = "III"
Output: [0,1,2,3]

Example 3:

Input: s = "DDI"
Output: [3,2,0,1]

Constraints:

1 <= s.length <= 10^5
s[i] is either 'I' or 'D'.

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def diStringMatch(s):
    low, high = 0, len(s)
    res = []
    for ch in s:
        if ch == 'I':
            res.append(low)
            low += 1
        else:  # 'D'
            res.append(high)
            high -= 1
    res.append(low)  # low == high now
    return res
Explaination:
This is Two Pointers (Greedy) approach

  1. Initialization :

    • low = 0, high = len(s): Pointers to track the smallest and largest remaining numbers available.
    • res = []: Stores the permutation result.

  2. Loop through string s :

    • For each character ch in s:
      • If ch is 'I' (increase): Append low to res and increment low by 1.
      • Else ('D' for decrease): Append high to res and decrement high by 1.

  3. Append last element :

    • Append low to res (at this point, low == high).

  4. Return result :

    • Return the permutation res that satisfies the 'I' and 'D' constraints.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def diStringMatch_stack(s):
    arr = list(range(len(s) + 1))
    i = 0
    while i < len(s):
        if s[i] == 'D':
            j = i
            while j < len(s) and s[j] == 'D':
                j += 1
            arr[i:j+1] = reversed(arr[i:j+1])
            i = j
        else:
            i += 1
    return arr
Explaination:
This is Stack Reversal approach

  1. Initialization :

    • arr = list(range(len(s) + 1)): Creates a list of numbers from 0 to len(s) in ascending order.
    • i = 0: Pointer to iterate through the string s.

  2. Loop through string s :

    • While i < len(s):
      • If s[i] == 'D':
        • Set j = i.
        • Move j forward while s[j] is 'D' to find the end of the consecutive 'D' sequence.
        • Reverse the subarray arr[i:j+1] to satisfy the descending order requirement.
        • Set i = j to continue processing after the reversed section.
      • Else ('I'): Increment i by 1 to move to the next character.

  3. Return result :

    • Return the modified list arr which satisfies the 'I' and 'D' pattern in s.

5. Bag of Tokens (Leetcode:948)

Problem Statement

You start with an initial power of power, an initial score of 0, and a bag of tokens given as an integer array tokens, where each tokens[i] denotes the value of tokeni.

Your goal is to maximize the total score by strategically playing these tokens. In one move, you can play an unplayed token in one of the two ways (but not both for the same token):

Face-up: If your current power is at least tokens[i], you may play tokeni, losing tokens[i] power and gaining 1 score.
Face-down: If your current score is at least 1, you may play tokeni, gaining tokens[i] power and losing 1 score.

Return the maximum possible score you can achieve after playing any number of tokens.

Example 1:

Input: tokens = [100], power = 50
Output: 0
Explanation: Since your score is 0 initially, you cannot play the token face-down. You also cannot play it face-up since your power (50) is less than tokens[0] (100).

Example 2:

Input: tokens = [200,100], power = 150
Output: 1
Explanation: Play token1 (100) face-up, reducing your power to 50 and increasing your score to 1.
There is no need to play token0, since you cannot play it face-up to add to your score. The maximum score achievable is 1.

Example 3:

Input: tokens = [100,200,300,400], power = 200
Output: 2
Explanation: Play the tokens in this order to get a score of 2:
Play token0 (100) face-up, reducing power to 100 and increasing score to 1.
Play token3 (400) face-down, increasing power to 500 and reducing score to 0.
Play token1 (200) face-up, reducing power to 300 and increasing score to 1.
Play token2 (300) face-up, reducing power to 0 and increasing score to 2.
The maximum score achievable is 2.

Constraints:

0 <= tokens.length <= 1000
0 <= tokens[i], power < 104

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def bagOfTokensScore(tokens, power):
    tokens.sort()
    left, right = 0, len(tokens) - 1
    score = max_score = 0

    while left <= right:
        if power >= tokens[left]:
            power -= tokens[left]
            score += 1
            left += 1
            max_score = max(max_score, score)
        elif score > 0:
            power += tokens[right]
            score -= 1
            right -= 1
        else:
            break
    return max_score
Explaination:
This is two pointer (greedy) approach

  1. Sort tokens :

    • tokens.sort(): Sorts tokens in ascending order to use the smallest token for gaining score and the largest for regaining power.

  2. Initialization :

    • left, right = 0, len(tokens) - 1: Two pointers for the smallest and largest remaining tokens.
    • score = 0: Current score.
    • max_score = 0: Maximum score achieved so far.

  3. Process tokens :

    • While left <= right:
      • If power >= tokens[left]:
        • Play the smallest token face up: reduce power by tokens[left], increase score by 1, move left pointer right.
        • Update max_score = max(max_score, score).
      • Else if score > 0:
        • Play the largest token face down: increase power by tokens[right], decrease score by 1, move right pointer left.
      • Else:
        • Break the loop if neither action is possible.

  4. Return result :

    • Return max_score, the highest score obtained during the process. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def bagOfTokensScore_bruteforce(tokens, power):
    max_score = 0
    def dfs(remaining, p, s):
        nonlocal max_score
        max_score = max(max_score, s)
        for i, t in enumerate(remaining):
            new_remaining = remaining[:i] + remaining[i+1:]
            if p >= t:  # face-up
                dfs(new_remaining, p - t, s + 1)
            if s >= 1:  # face-down
                dfs(new_remaining, p + t, s - 1)
    dfs(tokens, power, 0)
    return max_score
Explaination:
This is Brute-force approach

  1. Initialization :

    • max_score = 0: Tracks the highest score obtained during the search.

  2. Depth-first search (DFS) function :

    • dfs(remaining, p, s):
      • remaining: List of tokens not yet played.
      • p: Current available power.
      • s: Current score.
      • Update max_score = max(max_score, s) to record the best score so far.

  3. Explore choices for each token :

    • Loop through each token t in remaining:
      • Create a new list new_remaining excluding the chosen token.
      • If p >= t (enough power), simulate playing the token face-up:
        • Call dfs(new_remaining, p - t, s + 1).
      • If s >= 1 (enough score), simulate playing the token face-down:
        • Call dfs(new_remaining, p + t, s - 1).

  4. Return result :

    • Start DFS with dfs(tokens, power, 0).
    • Return max_score, the maximum achievable score after exploring all play orders.

6. Next Permutation (Leetcode:31)

Problem Statement

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

  • For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

  • For example, the next permutation of arr = [1,2,3] is [1,3,2].
  • Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
  • While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 100

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def nextPermutation(self, nums: List[int]) -> None:
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        j = i + 1
        while j < n and nums[j] > nums[i]:
            j += 1
        nums[i], nums[j-1] = nums[j-1], nums[i]

    nums[i+1:] = sorted(nums[i+1:])
    return nums
Explaination:
This is sort from pivot approach

  1. Initialization :

    • n = len(nums): Stores the total number of elements in nums.
    • i = n - 2: Starts from the second last index to find the first decreasing element from the right.

  2. Find pivot :

    • While i >= 0 and nums[i] >= nums[i + 1]: Move i leftwards to find the first element that is smaller than its next element.

  3. Swap with next greater element :

    • If i >= 0:
      • Initialize j = i + 1 and move it rightwards while nums[j] > nums[i].
      • Swap nums[i] with nums[j - 1] (the smallest element greater than nums[i] to the right).

  4. Rearrange suffix :

    • Sort the subarray nums[i+1:] to get the smallest lexicographic order for the suffix.

  5. Return result :

    • Return the modified nums which now represents the next lexicographical permutation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def nextPermutation(self, nums: List[int]) -> None:
    n = len(nums)

    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]: 
        i -= 1

    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]

    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
Explaination:
This is optimal in-place (two pointer) approach

  1. Initialization :

    • n = len(nums): Stores the total number of elements in nums.
    • i = n - 2: Starts from the second last index to find the first decreasing element from the right.

  2. Find pivot :

    • While i >= 0 and nums[i] >= nums[i + 1]: Move i leftwards until an element smaller than its next element is found.

  3. Swap with next greater element :

    • If i >= 0:
      • Set j = n - 1 and move it leftwards until nums[j] > nums[i].
      • Swap nums[i] and nums[j] (placing the next larger number in the pivot position).

  4. Reverse suffix :

    • Initialize left = i + 1 and right = n - 1.
    • While left < right: Swap nums[left] and nums[right], then move left forward and right backward.
    • This ensures the suffix after position i is in ascending order (smallest possible arrangement).

  5. Result :

    • nums is now rearranged to the next lexicographical permutation in-place.

7. 3Sum (Leetcode:15)

Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

Code and Explaination 

 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
def threeSum(nums):
    nums.sort()
    res = []

    for i in range(len(nums) - 2):
        # Skip duplicates for i
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = len(nums) - 1

        while left < right:
            curr_sum = nums[i] + nums[left] + nums[right]

            if curr_sum == 0:
                res.append([nums[i], nums[left], nums[right]])
                # Skip duplicates for left and right
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                left += 1
                right -= 1

            elif curr_sum < 0:
                left += 1
            else:
                right -= 1

    return res
Explaination:
This is first approach

  1. Sort the array :

    • nums.sort(): Sorts the list in ascending order to enable the two-pointer approach and easy duplicate handling.

  2. Initialize result list :

    • res = []: Stores unique triplets that sum to zero.

  3. Loop to fix the first element :

    • For i from 0 to len(nums) - 3:
      • Skip duplicates for the first element by checking if i > 0 and nums[i] == nums[i - 1].

  4. Two-pointer search for the other two elements :

    • Set left = i + 1 and right = len(nums) - 1.
    • While left < right:
      • Compute curr_sum = nums[i] + nums[left] + nums[right].
      • If curr_sum == 0:
        • Append the triplet [nums[i], nums[left], nums[right]] to res.
        • Skip duplicates for left and right pointers.
        • Move both pointers inward (left += 1, right -= 1).
      • Else if curr_sum < 0: Move left pointer right to increase the sum.
      • Else: Move right pointer left to decrease the sum.

  5. Return result :

    • Return res, the list of all unique triplets with sum equal to zero.

8: Three Sum Closest(Leetcode:16)

Problem Statement

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Constraints:

3 <= nums.length <= 500
-1000 <= nums[i] <= 1000
-10^4 <= target <= 10^4

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        closest_sum = float('inf')  # Start with a large value

        for i in range(n - 2):
            left, right = i + 1, n - 1

            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]

                # If this sum is closer to the target, update closest_sum
                if abs(current_sum - target) < abs(closest_sum - target):
                    closest_sum = current_sum

                if current_sum < target:
                    left += 1  # Need a larger sum
                elif current_sum > target:
                    right -= 1  # Need a smaller sum
                else:
                    return current_sum  # Exact match

        return closest_sum
Explaination:
This is first approach

1
Explaination:
This is second approach

9. Sentence Similarity III (Leetcode:1813)

Problem Statement

You are given two strings sentence1 and sentence2, each representing a sentence composed of words. A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of only uppercase and lowercase English characters.

Two sentences s1 and s2 are considered similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal. Note that the inserted sentence must be separated from existing words by spaces.

For example,

  • s1 = "Hello Jane" and s2 = "Hello my name is Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in s1.

  • s1 = "Frog cool" and s2 = "Frogs are cool" are not similar, since although there is a sentence "s are" inserted into s1, it is not separated from "Frog" by a space.

Given two sentences sentence1 and sentence2, return true if sentence1 and sentence2 are similar. Otherwise, return false.

Example 1:

Input: sentence1 = "My name is Haley", sentence2 = "My Haley"
Output: true
Explanation:
sentence2 can be turned to sentence1 by inserting "name is" between "My" and "Haley".

Example 2:

Input: sentence1 = "of", sentence2 = "A lot of words"
Output: false
Explanation:
No single sentence can be inserted inside one of the sentences to make it equal to the other.

Example 3:

Input: sentence1 = "Eating right now", sentence2 = "Eating"
Output: true
Explanation:
sentence2 can be turned to sentence1 by inserting "right now" at the end of the sentence.

Constraints:

1 <= sentence1.length, sentence2.length <= 100
sentence1 and sentence2 consist of lowercase and uppercase English letters and spaces.
The words in sentence1 and sentence2 are separated by a single space.

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def areSentencesSimilar(sentence1, sentence2):
    w1 = sentence1.split()
    w2 = sentence2.split()

    if len(w1) < len(w2):
        w1, w2 = w2, w1

    i, j = 0, 0
    while i < len(w2) and w1[i] == w2[i]:
        i += 1

    while j < len(w2) - i and w1[-(j+1)] == w2[-(j+1)]:
        j += 1

    return i + j == len(w2)
Explaination:
This is optimal(two pointer) approach

  1. Split sentences into words :
    • w1 = sentence1.split(), w2 = sentence2.split(): Convert both sentences into lists of words.
  2. Ensure w1 is the longer sentence :
    • If len(w1) < len(w2), swap w1 and w2.
  3. Match from the start :
    • Initialize i = 0.
    • While i < len(w2) and w1[i] == w2[i], increment i to count matching words from the beginning.
  4. Match from the end :
    • Initialize j = 0.
    • While j < len(w2) - i and w1[-(j+1)] == w2[-(j+1)], increment j to count matching words from the end.
  5. Check similarity condition :
    • If i + j == len(w2), return True (all words in w2 match either at the start or end of w1).
    • Otherwise, return False. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def areSentencesSimilar_bruteforce(sentence1, sentence2):
    w1 = sentence1.split()
    w2 = sentence2.split()

    # Ensure w1 is longer
    if len(w1) < len(w2):
        w1, w2 = w2, w1

    n1, n2 = len(w1), len(w2)

    for i in range(n2 + 1):  # prefix length
        for j in range(n2 - i + 1):  # suffix length
            if i + j <= n2 and w1[:i] == w2[:i] and w1[-j:] == w2[-j:]:
                return True
    return False
Explaination:
This is Brute-force approach

  1. Split sentences into words :

    • w1 = sentence1.split(), w2 = sentence2.split(): Convert both sentences into lists of words.

  2. Ensure w1 is the longer sentence :

    • If len(w1) < len(w2), swap w1 and w2.

  3. Store lengths :

    • n1 = len(w1), n2 = len(w2): Store lengths of both word lists for easy reference.

  4. Check all prefix-suffix combinations :

    • Loop i from 0 to n2 (possible prefix lengths).
    • For each i, loop j from 0 to n2 - i (possible suffix lengths).
    • If i + j <= n2 and both conditions hold:
      • w1[:i] == w2[:i] (prefix match)
      • w1[-j:] == w2[-j:] (suffix match)
        → Return True.

  5. Return result :

    • If no valid prefix-suffix combination is found, return False. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from collections import deque
def areSentencesSimilar_optimal(sentence1, sentence2):
    dq1 = deque(sentence1.split())
    dq2 = deque(sentence2.split())

    while dq1 and dq2 and dq1[0] == dq2[0]:
        dq1.popleft()
        dq2.popleft()

    while dq1 and dq2 and dq1[-1] == dq2[-1]:
        dq1.pop()
        dq2.pop()

    return not dq1 or not dq2
Explaination:
This is deque approach

  1. Convert sentences to deques :

    • dq1 = deque(sentence1.split()), dq2 = deque(sentence2.split()): Split each sentence into words and store them in deque for efficient pops from both ends.

  2. Match words from the start :

    • While both deques are non-empty and their first words match (dq1[0] == dq2[0]):
      • Remove the first word from both (popleft()).

  3. Match words from the end :

    • While both deques are non-empty and their last words match (dq1[-1] == dq2[-1]):
      • Remove the last word from both (pop()).

  4. Return similarity result :

    • If either deque is empty (not dq1 or not dq2), return True (all words in the shorter sentence match either at the start or end of the longer one).
    • Otherwise, return False.

10. Reverse Words in a String (Leetcode:151)

Problem Statement

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = " hello world "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

1 <= s.length <= 104
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def reverseWords(self, s: str) -> str:
    res = []
    left = right = len(s) - 1

    while left >= 0:
        # Skip trailing spaces
        while left >= 0 and s[left] == " ":
            left -= 1
        if left < 0:
            break

        right = left
        # Move left to the start of the word
        while left >= 0 and s[left] != " ":
            left -= 1

        # Append the word
        res.append(s[left+1:right+1])

    return " ".join(res)
Explaination:
This is first approach

  1. Initialization :

    • res = []: List to store extracted words in reverse order.
    • left = right = len(s) - 1: Pointers starting at the last character of the string.

  2. Process words from end to start :

    • While left >= 0:
      • Skip trailing spaces by moving left leftwards while s[left] == " ".
      • If left < 0, break the loop (no more words).

  3. Identify a word :

    • Set right = left (marks the end of the current word).
    • Move left leftwards until a space is found or the start of the string is reached (s[left] != " ").

  4. Store the word :

    • Append the substring s[left+1:right+1] (the current word) to res.

  5. Return result :

    • Join the words in res with a single space (" ".join(res)) and return the reversed sentence without extra spaces. 

1
2
def reverseWords(self, s: str) -> str:
    return " ".join(s.split()[::-1])
Explaination:
This approach uses built-in method

Sliding Window

When to Use

  • Ideal for problems involving contiguous subarrays or substrings, such as finding maximum sums, longest substring without repeats, or counting subarrays with certain properties.

How It Works

  • Two pointers define a dynamic window: start and end.
  • The window expands or shrinks by moving pointers based on conditions (e.g., sum, uniqueness).
  • Efficiently processes elements in a linear pass without redundant checks.

1. Contains Duplicate III (Leetcode:220)

Problem Statement

You are given an integer array nums and two integers indexDiff and valueDiff.
Find a pair of indices (i, j) such that:
i != j,
abs(i - j) <= indexDiff.
abs(nums[i] - nums[j]) <= valueDiff, and
Return true if such pair exists or false otherwise.

Example 1:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

Example 2:

Input: nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
Output: false
Explanation: After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.

Constraints:

2 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
1 <= indexDiff <= nums.length
0 <= valueDiff <= 10^9

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from bisect import bisect_left, insort
class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        if valueDiff < 0 or indexDiff <= 0:
            return False

        window = []
        for i, num in enumerate(nums):
            # Find the smallest number >= num - valueDiff
            pos = bisect_left(window, num - valueDiff)

            # Check if it exists and satisfies valueDiff condition
            if pos < len(window) and abs(window[pos] - num) <= valueDiff:
                return True

            # Insert current number in sorted order
            insort(window, num)

            # Maintain window size
            if len(window) > indexDiff:
                window.pop(bisect_left(window, nums[i - indexDiff]))

        return False
Explaination:
This is sliding window + BST approach

 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
def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
    if valueDiff < 0:
        return False

    bucket = {}
    bucket_size = valueDiff + 1

    for i, num in enumerate(nums):
        bucket_id = num // bucket_size
        if num < 0:
            bucket_id -= 1

        # Check current bucket
        if bucket_id in bucket:
            return True

        # Check neighbor buckets
        if (bucket_id - 1 in bucket and abs(num - bucket[bucket_id - 1]) <= valueDiff):
            return True
        if (bucket_id + 1 in bucket and abs(num - bucket[bucket_id + 1]) <= valueDiff):
            return True

        bucket[bucket_id] = num

        # Maintain window size
        if i >= indexDiff:
            old_bucket_id = nums[i - indexDiff] // bucket_size
            if nums[i - indexDiff] < 0:
                old_bucket_id -= 1
            del bucket[old_bucket_id]

    return False
Explaination:
This is Bucket sort Hashing approach

2. Longest Repeating Character Replacement (Leetcode:424)

Problem Statement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

Constraints:

1 <= s.length <= 10^5
s consists of only uppercase English letters.
0 <= k <= s.length

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def characterReplacement(s, k):
    freq = [0] * 26
    left = 0
    max_freq = 0
    ans = 0

    for right in range(len(s)):
        freq[ord(s[right]) - ord('A')] += 1
        max_freq = max(max_freq, freq[ord(s[right]) - ord('A')])

        while (right - left + 1) - max_freq > k:
            freq[ord(s[left]) - ord('A')] -= 1
            left += 1

        ans = max(ans, right - left + 1)

    return ans
Explaination:
This is optimal sliding window approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
from collections import defaultdict

def characterReplacement(s, k):
    count = defaultdict(int)
    left = 0
    max_freq = 0
    ans = 0

    for right in range(len(s)):
        count[s[right]] += 1
        max_freq = max(max_freq, count[s[right]])

        while (right - left + 1) - max_freq > k:
            count[s[left]] -= 1
            left += 1

        ans = max(ans, right - left + 1)

    return ans
Explaination:
This is sliding window + dictionary approach

Divide and Conquer

1. Rotate Array (Leetcode:189)

Problem Statement

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Example 2:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Constraints:

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 ^- 1
0 <= k <= 10^5

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def rotate(nums, k):
    n = len(nums)
    k %= n  # Handle 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)        # Step 1: Reverse entire array
    reverse(0, k - 1)        # Step 2: Reverse first k elements
    reverse(k, n - 1)        # Step 3: Reverse rest
Explaination:
This is optimal approach

  1. Initialization :

    • n = len(nums): Stores the total number of elements in nums.
    • k %= n: Adjusts k to handle cases where k is greater than n.

  2. Helper function reverse(start, end) :

    • Swaps elements from index start to end while moving pointers inward.

  3. Rotation steps :

    • reverse(0, n - 1): Reverse the entire array.
    • reverse(0, k - 1): Reverse the first k elements.
    • reverse(k, n - 1): Reverse the remaining n - k elements.

  4. Result :

    • The array nums is rotated to the right by k steps in-place.

1
2
3
4
5
6
7
def rotate_extra_array(nums, k):
    n = len(nums)
    k %= n
    arr = [0] * n
    for i in range(n):
        arr[(i + k) % n] = nums[i]
    nums[:] = arr
Explaination:
This is second approach

  1. Initialization :

    • n = len(nums): Stores the total number of elements in nums.
    • k %= n: Adjusts k to handle cases where k is greater than n.
    • arr = [0] * n: Creates a new array of size n initialized with zeros.

  2. Positioning elements :

    • For each index i in nums:
      • Place nums[i] into its new position (i + k) % n in arr.

  3. Copy back to original :

    • nums[:] = arr: Copies the rotated result from arr back into nums in-place.

  4. Result :

    • The array nums is rotated to the right by k steps using extra space of size n.