Two_Pointers

3 posts with the tag “Two_Pointers”

Leetcode 27: Remove Element

May 15, 2025

Question

In this Leetcode problem, we are given an array named nums and a number named val. The number val represents the value we want to remove from the given nums array. For example, if we have an array nums = [1,2,3,4,5], and a val = 2, then we want nums to be [1,3,4,5] with the element 2 removed. Only the first K elements of the nums array is checked to ensure all elements equal to val have been removed.

K is used to represent the amount of elements from the beginning of the array that are checked by the Custom Leetcode Judge for this problem. This means values in nums beyond index k are ignored by the Leetcode Judge. Only the section of nums, 0 to K, need to be edited in-place by our algorithm solution.

The first K elements of nums are checked to ensure you removed the val from the starting prefix of the array. Secondly, the Leetcode Judge checks that your solution returned the amount of elements not equal to val. This means that we want to edit the nums array in-place, as well as return the amount of elements not equal to val.

Lastly, it is important to note that technically, you do not need to worry about the order of your nums array, just that the first K elements don’t include the value of val. This is because the custom judge actually sorts your nums array behind the scenes when evaluating your solution.

Solving

To solve this problem, I implemented a two pointer solution to edit elements of nums in-place, as well as keep track of the amount of elements not equal to val. I use an index variable named J to check indexs of nums, alongside the count of elements that aren’t equal to val. For each number of nums that is not equal to val, I edit the element at index J to that value, while also incrementing J to move to the next slot. Index J is used for editing specific elements of the nums array, as well as keeping track of how many elements I have found that are not equal to val. By the end, the nums array is successfully modified in-place. My solution finishes executing by returning the value of J, which represents the number of elements in nums not equal to val.

TLDR

I used a two pointer solution to edit in-place the values of nums to avoid including the value of val. At the end, I return the index J to represent the amount of elements I found from the array nums that don’t equal val. This solution satisfies the custom leetcode judge conditions of editing the nums array in-place and returning the amount of elements from nums not equal to val.

Leetcode 88: Merge Sorted Array

May 14, 2025

DevGod

Elf Vtuber

Question

In this Leetcode Problem, we are given two already sorted arrays, as well as their expected sizes in the m and n variables. The Nums1 array is also filled with zeros at the end to ensure the Nums2 array can fit inside of Nums1.

Our task is to merge both of these presorted arrays together Inplace inside of Nums1, while maintaining a sorted ordering. Inplace is different from most Leetcode problems, as we are only required to edit the given nums1 array. Instead of checking a specific function return value, the Leetcode Judge instead checks what we have done with the given nums1.

Additional, the Follow Up challenge specifies we want to solve this problem in O(m+n) time. The easy (m+n) log(n) solution would be to concatenate the given arrays together, then sort them using a built-in sort function. However, because most built-in sorting methods are log(n) time complexity, this would break our follow up challenge. Instead, we can use a more optimal two pointer approach.

Solving

To solve this problem, we use an I variable to iterate from right to left on the nums1 array. We then use two pointers named a,b as a way to check values from the two given arrays. The pointer a is used to look up values in nums1, and the pointer b is used for numbers in nums2. So where the I variable is just for iterating through nums1, a and b are actually used for performing our comparisons.

If nums1[a] is greater then nums2[b], then we can keep that value at nums1 the same. Note that we only check this if our a pointer is still at a valid slot in nums1. Otherwise, we can safely assume that the current I th position in nums1 needs to be replaced with nums2[b]. Since nums2 is guaranteed to be the smaller length of the two given arrays, we can exit out of our while loop.

Instead of returning an array, we can just let the code end at the while loop, as the Leetcode Judge is only concerned with what nums1 is equal to.

TLDR:

We must merge two given sorted arrays together inplace. To solve the follow up challenge of O(m+n) time complexity, we can easily do this using a two pointer solutions instead of relying on built in sorting methods.

Leetcode 763: Partition Labels

Mar 28, 2025

DevGod

Elf Vtuber

For today’s daily leetcode problem, we are given a string and need to split it into as many partitions as possible, ensuring that each letter appears in at most one partition. Additionally, the partitions must preserve the order of letters as they appear in the original string. However, we don’t need to store the actual substrings—our task is simply to return the lengths of these partitions.

Example Walkthrough Consider the string “pizzatime”. The optimal partitions would be [1,6,1,1]. Here’s why:

The letters p, m, and e each form their own single-letter partitions since they don’t share any letter with another partition.
The substring “izzati” forms a partition because it contains multiple occurrences of i and z, and we need to ensure that all instances of a letter belong to a single partition.
Since the letters must remain in order and cannot belong to multiple partitions, “zzati” is grouped together with i to form a partition of length 6.

Another example is “partitionlabels”, which results in [1,13,1]:

The letters p and s form their own separate partitions.
The middle partition, “artitionlabel”, must include all occurrences of a and l.
Since l appears late in the string, we must extend the partition to ensure all ls are included, resulting in a large middle partition.

Implementation Approach Since I was in a hurry and the constraints were small, I used JavaScript’s built-in .lastIndexOf() method to determine the last occurrence of each letter in real time. The key insight is that a letter’s last occurrence dictates where a partition must end. While this approach runs in 𝑂(n^2) time due to repeated .lastIndexOf() calls, an optimized solution could use a hashmap for 𝑂(1) lookups.

To efficiently track when to end a partition, I maintain a max variable, representing the farthest last occurrence seen so far. As I iterate through the string, I update max using:

max = Math.max(max, s.lastIndexOf(s[L]));

This ensures that if a previous letter has a later last occurrence, we extend the current partition accordingly. This is crucial for cases like “partitionlabels”, where encountering l extends the partition beyond a’s last occurrence.

I iterate through the string using a loop and keep track of partitionSize. Whenever I reach max, I add partitionSize to the result array, reset it, and continue. Instead of constructing substrings, I only track partition lengths, as that’s all the problem requires.

This greedy approach ensures an optimal partitioning of the string while keeping the implementation simple and efficient.