🗓️ LeetCode Daily Challenge – Day 1

🔑 Prerequisite Knowledge:

Arrays – Key Points:

1. Array Structure:
   • Arrays are a collection of elements of the same type stored in contiguous memory.
   • Each element can be accessed using an index, starting from 0.
     
2. Memory:
   • Array elements are stored in continuous memory locations, which makes access fast but inserting or deleting elements slow, since other elements need to be shifted.
3. 2D Arrays:
   • In C++, 2D arrays are stored in continuous memory.
   • In Java, 2D arrays may not be stored continuously, as Java abstracts memory management.
4. Array Modifications:
   • Elements in an array cannot be deleted, only overwritten.
   • Shifting elements is needed when adding/removing, which can be inefficient.
     

🧠 LeetCode Problem 1: [704 Binary Search]

🚀 A. Problem Description:

You are given a sorted array of integers nums in ascending order and an integer target. Write a function to search for target in nums. If target exists, return its index. Otherwise, return -1.
Note: Your solution must have a time complexity of O(log n).

Example 1:

• Input: nums = [-1,0,3,5,9,12], target = 9
• Output: 4
• Explanation: 9 exists in nums and its index is 4.

Example 2:

• Input: nums = [-1,0,3,5,9,12], target = 2
• Output: -1
• Explanation: 2 does not exist in nums, so return -1.

Constraints:

• 1 ≤ nums.length ≤ 10⁴
• -10⁴ < nums[i], target < 10⁴
• All integers in nums are unique.
• nums is sorted in ascending order.

You can find the full problem description here. 👈

💡 B. Thought Process:

1. Understand the problem: 🤔
   • Efficiently search for the target in a sorted array using binary search with a time complexity of O(log n).
   • Binary search is ideal here since the array is sorted and has no duplicates, ensuring a unique result if the target is found.
   • The main challenge is managing the boundary conditions: deciding between while (left <= right) or while (left < right) and handling updates like right = middle vs. right = middle - 1.
2. Break it down:
   • 📥 Inputs: A sorted array nums and an integer target.
   • 📤 Outputs: The index of target in nums if found, otherwise -1.
   • 💭 Edge cases: The target may not exist in the array, or the array could have only one element.
3. Choose an approach:
   • Version 1: A linear search using a simple for loop.
   • Version 2: A binary search using a left-closed, right-closed interval [left, right].
   • Version 3: A binary search using a left-closed, right-open interval [left, right).

🔨 C. Approach 1: Brutal Force

📝 Plan:

In this approach, we use a basic linear search to find the target. This method involves looping through the array one element at a time to check if it matches the target. Though simple, it’s inefficient and has a time complexity of O(n), which is much slower than binary search, especially for large inputs.

• Step 1️⃣: Loop through the array using a for loop.
• Step 2️⃣: For each element in the array, check if it matches the target.
• Step 3️⃣: If found, return the index. If not, return -1 at the end.

🧮 Complexity:

• ⏳ Time complexity: O(n)
• 🗂️ Space complexity: O(1)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # Brutal search through each element
        for i in range(len(nums)):
            if nums[i] == target:
                return i  # Return index if found
        return -1  # Return -1 if not found

🔨 C. Approach 2: Binary Search (Left Closed, Right Closed Interval)

📝 Plan:

This version uses a left-closed, right-closed interval [left, right] to perform binary search.

• Step 1️⃣: Initialize left at 0 and right at len(nums) - 1.
• Step 2️⃣: Compute the middle index as left + (right - left) // 2.
• Step 3️⃣: If nums[middle] is the target, return the index. Otherwise, adjust the search interval:
  • If nums[middle] > target, narrow down the range to [left, middle - 1].
  • If nums[middle] < target, adjust the range to [middle + 1, right].

🧮 Complexity:

• ⏳ Time complexity: O(log n)
• 🗂️ Space complexity: O(1)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1  # Left-closed, right-closed interval

        while left <= right:
            middle = left + (right - left) // 2
            
            if nums[middle] > target:
                right = middle - 1  # Narrow down to [left, middle - 1]
            elif nums[middle] < target:
                left = middle + 1  # Narrow down to [middle + 1, right]
            else:
                return middle  # Target found
        return -1  # Target not found

🔨 C. Approach 3: Binary Search (Left Closed, Right Open Interval)

📝 Plan:

This version uses a left-closed, right-open interval [left, right) for binary search.

• Step 1️⃣: Initialize left at 0 and right at len(nums) (not len(nums) - 1).
• Step 2️⃣: Compute the middle index as left + (right - left) // 2.
• Step 3️⃣: Adjust the search interval:
  • If nums[middle] > target, the new interval becomes [left, middle].
  • If nums[middle] < target, the new interval becomes [middle + 1, right].

🧮 Complexity:

• ⏳ Time complexity: O(log n)
• 🗂️ Space complexity: O(1)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)  # Left-closed, right-open interval

        while left < right:  # Note that we use `<` here instead of `<=`
            middle = left + (right - left) // 2
            
            if nums[middle] > target:
                right = middle  # Narrow down to [left, middle)
            elif nums[middle] < target:
                left = middle + 1  # Narrow down to [middle + 1, right)
            else:
                return middle  # Target found
        return -1  # Target not found

🔎 D. Edge Cases:

• An empty array (nums = [])
• A target that’s smaller than the smallest or larger than the largest element.
• An array with only one element.

🔗 E. Similar Questions:

• 🔗 35. Search Insert Position (opens new window)
• 🔗 34. Find First and Last Position of Element in Sorted Array (opens new window)
• 🔗 69. Sqrt(x) (opens new window)
• 🔗 367. Valid Perfect Square (opens new window)

🧠 LeetCode Problem 2: [27 Remove Element]

🚀 A. Problem Description:

You are given an array nums and a value val. You need to remove all occurrences of val in the array in place and return the new length of the modified array. The order of elements can be changed, and it doesn’t matter what values exist beyond the new length. The operation must be done with O(1) extra space.

Example 1:

• Input: nums = [3, 2, 2, 3], val = 3
• Output: 2
• Explanation: After removing 3, the array is [2, 2], and the length is 2.

Example 2:

• Input: nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2
• Output: 5
• Explanation: After removing 2, the array is [0, 1, 3, 0, 4], and the length is 5.

Constraints:

• 0 ≤ nums.length ≤ 100
• 0 ≤ nums[i] ≤ 50
• 0 ≤ val ≤ 100

You can find the full problem description here. 👈

💡 B. Thought Process:

1. Understand the problem: 🤔
   • The problem asks us to remove all instances of a target value (val) from the array, and return the length of the remaining array.
   • We cannot allocate new space for another array. We need to modify the array in place, and the operation must be done with constant space.
2. Break it down:
   • 📥 Inputs: An array of integers nums and an integer val to be removed.
   • 📤 Outputs: The new length of the modified array. The first elements of the array must not include the removed values, but the order beyond this does not matter.
   • 💭 Edge cases:
     • The array may be empty, in which case the result should be 0.
     • The val may not exist in the array, in which case we simply return the length of the original array.
     • All elements may be equal to val, meaning the entire array needs to be “removed.”
3. Choose an approach:
   • Version 1: A brute-force approach where we remove each element matching val and shift the rest of the array forward. This would have a time complexity of O(n²) due to shifting.
   • Version 2: A more efficient solution using the two-pointer technique, where one pointer keeps track of elements to remove, and the other tracks elements to retain, with O(n) time complexity.

🔨 C. Approach 1: Brute Force

📝 Plan:

1. Use a loop to iterate over the array.
2. Every time an element matches val, shift all subsequent elements one position to the left, effectively “removing” the element.
3. Decrease the array size by 1 after each removal, and adjust the index to avoid skipping elements.

🧮 Complexity:

• ⏳ Time complexity: O(n²) – shifting elements makes this approach inefficient.
• 🗂️ Space complexity: O(1) – no extra space is used.

class Solution:
    def removeElement(self, nums: list[int], val: int) -> int:
        i, l = 0, len(nums)

        while i < l:
            if nums[i] == val:  # Find the target element
                for j in range(i + 1, l):  # Shift elements left
                    nums[j - 1] = nums[j]
                l -= 1  # Reduce size of the array
                i -= 1  # Adjust index to account for shifting
            i += 1

        return l  # Return the new length

🔨 C. Approach 2: Two-pointer Technique (Fast and Slow Pointers)

📝 Plan:

1. Initialize two pointers:
   • Fast pointer will scan the array for elements that are not equal to val.
   • Slow pointer will point to where the next valid (non-val) element should be placed.
2. As the fast pointer moves through the array, every time it finds a non-val element, it copies it to the slow pointer’s position and increments the slow pointer.
3. The fast pointer will continue until the end of the array, and the slow pointer will point to the new length of the modified array.

🧮 Complexity:

• ⏳ Time complexity: O(n) – the array is traversed only once.
• 🗂️ Space complexity: O(1) – no extra space is used.

class Solution:
    def removeElement(self, nums: list[int], val: int) -> int:
        fast = 0  # Fast pointer
        slow = 0  # Slow pointer
        size = len(nums)

        while fast < size:  # Avoid going out of bounds
            if nums[fast] != val:
                nums[slow] = nums[fast]  # Replace the value at slow pointer
                slow += 1  # Move slow pointer forward
            fast += 1  # Always move fast pointer

        return slow  # The new length of the array

🔨 C. Approach 3: Two-pointer Technique (Opposite Direction)

📝 Plan:

1. Set two pointers, left starting at the beginning and right starting at the end of the array.
2. Move the left pointer forward until it finds an element equal to val.
3. Move the right pointer backward until it finds an element not equal to val.
4. Swap the elements at the left and right pointers, then move both pointers inward.
5. Continue until the pointers meet. The left pointer will indicate the new length of the array.

🧮 Complexity:

• ⏳ Time complexity: O(n) – each element is processed at most once.
• 🗂️ Space complexity: O(1) – no additional space is used.

class Solution:
    def removeElement(self, nums: list[int], val: int) -> int:
        n = len(nums)
        left, right = 0, n - 1

        while left <= right:
            while left <= right and nums[left] != val:
                left += 1
            while left <= right and nums[right] == val:
                right -= 1
            if left < right:  # Swap elements
                nums[left] = nums[right]
                left += 1
                right -= 1

        return left  # New length of the array

🔎 D. Edge Cases:

• Empty array: If nums is an empty array, we should return 0 as the length.
• All elements equal to val: If all elements in the array are equal to val, we should return 0.
• No elements equal to val: In this case, we return the length of the original array since nothing is removed.

🔗 E. Similar Questions:

• 🔗 26. 删除排序数组中的重复项
• 🔗 283. 移动零
• 🔗 844. 比较含退格的字符串
• 🔗 977. 有序数组的平方

🧠 LeetCode Problem 3: [977 Squares of a Sorted Array]

🚀 A. Problem Description:

You are given a sorted array of integers nums in non-decreasing order. Return a new array where each element is the square of each number from nums, also in non-decreasing order.

Example 1:

• Input: nums = [-4, -1, 0, 3, 10]
• Output: [0, 1, 9, 16, 100]
• Explanation: After squaring, the array becomes [16, 1, 0, 9, 100]. Sorting results in [0, 1, 9, 16, 100].

Example 2:

• Input: nums = [-7, -3, 2, 3, 11]
• Output: [4, 9, 9, 49, 121]
• Explanation: After squaring, the array becomes [49, 9, 4, 9, 121]. Sorting results in [4, 9, 9, 49, 121].

Constraints:

• 1 ≤ nums.length ≤ 10⁴
• -10⁴ ≤ nums[i] ≤ 10⁴
• nums is sorted in non-decreasing order.

You can find the full problem description here. 👈

💡 B. Thought Process:

1. Understand the problem: 🤔
   • We are given a sorted array where both negative and positive numbers may exist. Squaring negative numbers can turn them into larger values than the positive numbers, so we need to handle this sorting properly after squaring.
2. Break it down:
   • 📥 Inputs: A sorted array of integers nums.
   • 📤 Outputs: A sorted array where each element is the square of the input numbers.
   • 💭 Edge cases:
     • All numbers are negative.
     • All numbers are positive.
     • The array contains zero.
3. Choose an approach:
   • Version 1: A simple brute-force solution where we first square each number and then sort the resulting array.
   • Version 2: Use a two-pointer technique to square elements starting from the outermost values (leftmost and rightmost), filling the result array in reverse order.

🔨 C. Approach 1: Brute-force Sorting

📝 Plan:

1. Square each element: Loop through the array and replace each element with its square.
2. Sort the squared array: Use the built-in sorting algorithm to sort the squared elements.

🧮 Complexity:

• ⏳ Time complexity: O(n log n)
• 🗂️ Space complexity: O(n)

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            nums[i] = nums[i] ** 2  # Square each number
        nums.sort()  # Sort the squared numbers
        return nums

🔨 C. Approach 2: Two-pointer Technique

📝 Plan:

1. Initialize two pointers: Start one pointer left at the beginning and another pointer right at the end of the array.
2. Compare absolute values: At

each step, compare the absolute values of the numbers at both pointers.

• Square the larger number and place it at the end of the result array.
• Move the corresponding pointer inward.

3. Fill the result array: Continue this process until all elements are processed.

🧮 Complexity:

• ⏳ Time complexity: O(n)
• 🗂️ Space complexity: O(n)

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l, r, i = 0, len(nums)-1, len(nums)-1
        res = [0] * len(nums)  # Result array of the same size

        while l <= r:
            if abs(nums[l]) > abs(nums[r]):
                res[i] = nums[l] ** 2
                l += 1
            else:
                res[i] = nums[r] ** 2
                r -= 1
            i -= 1  # Fill result array from the end

        return res

🔎 D. Edge Cases:

• An array with all negative values, like [-5, -3, -1].
• An array with all positive values, like [1, 2, 3].
• An array containing zero, like [-2, 0, 2].

🔗 E. Similar Questions:

• 🔗 5. Search Insert Position
• 🔗 67. Sqrt(x)