two pointers

Question 1

move zeros
theory

Answer 1

1. Initialize a Pointer (last_non_zero_found_at):

The variable last_non_zero_found_at keeps track of the position where the next non-zero element should be placed.
It starts at index 0 because that is the first valid position where a non-zero element should be placed.
2. Iterate Through the Array (cur):

A for loop runs through each element in the array using the cur variable, which represents the current index of the array.

3. Check if Current Element is Non-zero:

For each element nums[cur], check if it is non-zero.
If it is a non-zero element, swap it with the element at the last_non_zero_found_at position. This effectively moves non-zero elements to the front of the array.

4. Swap the Elements:

The swap between nums[last_non_zero_found_at] and nums[cur] ensures that the non-zero elements are moved to the front of the array while pushing any zero encountered earlier into the position where the non-zero element was.
After the swap, the last_non_zero_found_at is incremented by 1 to indicate that the next non-zero element should go into the next position.

5. Result:

Once the loop finishes, all the non-zero elements will have been moved to the front of the array, and the zeros will be pushed to the end.

Question 2

move zeroes
code

Answer 2

def moveZeroes(self, nums: List[int]) -> None:
last_non_zero_found_at = 0
for cur in range(len(nums)):
if nums[cur] != 0:
nums[last_non_zero_found_at], nums[cur] = nums[cur], nums[last_non_zero_found_at]
last_non_zero_found_at += 1

Question 3

is subsequence
theory

Answer 3

1. Initialization:

Two pointers i and j are initialized to 0. i is used to track the position in string s, and j tracks the position in string t.

2. While Loop:

The loop runs as long as both pointers are within the bounds of their respective strings (i.e., i < len(s) and j < len(t)).
Inside the loop, it checks if the current characters in s and t are equal (s[i] == t[j]).
If they are equal, it means the current character in s matches a character in t, so it moves the pointer i to the next character in s.
Regardless of whether the characters match or not, the pointer j always moves to the next character in t.

3. Final Check:

After the loop, the function checks whether i has reached the end of string s (i == len(s)).
If this is true, it means all characters in s were found in t in the correct order, so the function returns True.
If i does not reach the end of s, it means some characters in s were not found in t, so the function returns False.

Question 4

isSubsequence
code

Answer 4

def isSubsequence(self, s: str, t: str) -> bool:
i, j = 0, 0 # Initialize pointers for s and t
while i < len(s) and j < len(t):
if s[i] == t[j]: # Check if current characters match
i += 1 # Move pointer in s
j += 1 # Always move pointer in t

    # Check if all characters in s were found in t
    return i == len(s)

Question 5

container with most water
theory

Answer 5

The algorithm uses a greedy approach by starting with the widest possible container (the two ends of the array) and moving the pointers inward. Since the area depends on both the height of the shorter line and the width, the algorithm tries to find a taller line by moving the pointer that is currently at the shorter height.

The time complexity of this solution is O(n) because each pointer is moved at most n times, where n is the length of the array

Question 6

container with most water
code

Answer 6

class Solution:
def maxArea(self, height: List[int]) -> int:
area = 0
left, right = 0, len(height)-1
while (left < right):
width = right - left
heighta = min(height[right], height[left])
area = max(area, width*heighta)
if height[left] <= height[right]:
left += 1
else:
right -=1

    return area

Question 7

max number of k sum pairs
theory

Answer 7

Sort the nums list.
Use two pointers (left and right) to find pairs that sum to k.
If a pair is found, increment the operation counter and move both pointers inward.
If the sum is too small, move the left pointer right to increase the sum.
If the sum is too large, move the right pointer left to decrease the sum.
Return the total number of valid pairs found.

Question 8

max number of k sum pairs
code

Answer 8

def maxOperations(self, nums: List[int], k: int) -> int:
nums.sort()

    left = 0 
    right = len(nums) - 1
    operation = 0 

    while left < right:
        if ((nums[left] + nums[right]) == k):
            operation += 1
            left +=1 
            right -=1
        elif((nums[left] + nums[right]) < k):
            left += 1
        else:
            right -= 1
    return operation

Question 9

container with most water
step by step

Answer 9

1. Initialize Two Pointers:

Start with two pointers: one at the beginning of the array (left = 0) and one at the end (right = n - 1), where n is the length of the height array.

2. Calculate Area:

For each pair of lines represented by the two pointers left and right, calculate the area of the container formed by those two lines and the x-axis.
The area between two lines is determined by:

Area=min(height[left],height[right])×(right−left)

• The height of the container is determined by the shorter of the two lines (since the water can’t overflow the shorter line).
• The width of the container is the distance between the two pointers (right - left).

3. Track Maximum Area:

Keep a variable max_area to store the maximum area encountered so far. After each calculation, update max_area if the current area is greater than the previously stored value.

4. Move the Pointers:

To try and find a potentially larger container, move the pointer pointing to the shorter line:

If height[left] < height[right], increment the left pointer to explore a potentially taller line on the left side.

If height[right] <= height[left], decrement the right pointer to explore a potentially taller line on the right side.

Continue this process until the two pointers meet.

5. End Condition:

The algorithm stops when left and right pointers meet, as no more containers can be formed.