DEV Community: Simona Cancian

Leetcode Day 9: Find the Index of the First Occurrence in a String Explained

Simona Cancian — Thu, 11 Jul 2024 05:44:26 +0000

The problem is as follows:

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

This is how I solved it:

This is the first easy problem that was actually easy. Just use the built-in index() function, and that's it!
This is how it works:

Check if 'needle' is a substring of 'haystack'
If it is, return the index of the first occurrence of 'needle'
Else if 'needle' is not found, return -1

if needle in haystack:
    return haystack.index(needle)
else:
    return -1

This is the completed solution:

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.index(needle) if needle in haystack else -1

Leetcode Day 8: Remove Element Explained

Simona Cancian — Tue, 09 Jul 2024 02:10:40 +0000

The problem is as follows:

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Here is how I solved it:

To solve this problem, I used two main strategies:

In-place Replacement: Instead of creating a new array to store the elements that are not equal to val, use the same array nums to overwrite the elements that need to be removed.
Two-pointer Technique: One pointer (i) iterates through each element in the array, and another pointer (k) keeps track of the position where the next non-val element should be placed.

First, initialize a pointer k and set it to 0. This will keep track of the position where the next non-val element should be placed.

class Solution:
def removeElement(self, nums: List[int], val: int) -> int:       
    k = 0

Iterate through nums array.
Check if the current element nums[i] is different from val to keep track of k.
If it is, move element nums[i] to the k-th position, and increment k by 1 to update the position for the next non-val element.

for i in range(len(nums)):
    if nums[i] != val:
        nums[k] = nums[i]
        k += 1

Return k, which is the number of elements not equal to val.

return k

Here is the completed solution:

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        k = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[k] = nums[i]
                k += 1
        return k

Leetcode Day 7: Remove Duplicated from Sorted Array Explained

Simona Cancian — Mon, 08 Jul 2024 03:25:02 +0000

The problem is as follows:

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return t_he number of unique elements in nums_.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Here is how I solved it:

First, initialize a pointer k and set it to 0. This pointer will keep track of the position of the last unique element in the array.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # Initialize a pointer 'k' and set it to 0
        k = 0

Loop through nums array from the second element (index 1). The first element is always unique, so we can skip it for comparison purposes.
Check for duplicates: if the current element nums[i] is different from the last unique element nums[k].
If it is, it means we have found a new unique element. Move to the next element and update nums[k] to current element nums[i].

for i in range(1, len(nums)):
    if nums and nums[i] != nums[k]:
        k += 1
        nums[k] = nums[i]

After the loop, k will be the index of the last unique element, so the total number of unique elements is k + 1. Return k + 1 because k starts at 0'

return k + 1

Here is the completed solution:

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k = 0
        for i in range(1, len(nums)):
            if nums and nums[i] != nums[k]:
                k += 1
                nums[k] = nums[i]
        return k + 1

Leetcode Day 6: Merge Two Sorted Lists Explained

Simona Cancian — Sun, 07 Jul 2024 00:35:13 +0000

The problem is as follows:
You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:



Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:



Input: list1 = [], list2 = []
Output: []

Example 3:



Input: list1 = [], list2 = [0]
Output: [0]

Here is how I solved it:
Let's go through the provided definition for a singly-linked list:



class ListNode:
    def __init__(self, val=0, next=None):
        # Data stored in node val
        self.val = val
        # Reference to the next node
        self.next = next

A singly linked list is a linear data structure where elements are connected in a sequence, and each element points to the next one using a pointer.

With that said, let's step through the logic here.

Initialize a dummy_node that represents the starting point for the new merges sorted list.
Set it to a pointer current_node (address in RAM, aka a variable) to construct the new list. Initially, this pointer will point to the dummy node. ```

class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy_node = ListNode()
current_node = dummy_node

- Use a while loop to iterate through both lists at the same time until of them is null.
- Choose the head with the smaller value of the two lists: if value of current node in `list1` is less than value of node in `list2`, then append the `list1` node to the merged list and move to next node in `list1`.
- Else, append the `list2` node to merged list and move to next node in `list2`.
- We are still in the while loop. Move the current_node pointer to the newly added node

while list1 and list2:
if list1.val < list2.val:

current_node.next = list1
list1 = list1.next
else:
current_node.next = list2
list2 = list2.next

current_node = current_node.next


- After the while loop, if there are remaining nodes in `list1` or `list2`, append them to the merged list.
- Return the head of the merged list, which is the next node of the dummy node.

if list1:
current_node.next = list1
else:
current_node.next = list2

return dummy_node.next

Here is the completed solution:

class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy_node = ListNode()
current_node = dummy_node

    while list1 and list2:
        if list1.val < list2.val:
            current_node.next = list1
            list1 = list1.next
        else:
            current_node.next = list2
            list2 = list2.next

        current_node = current_node.next

    if list1:
        current_node.next = list1
    else:
        current_node.next = list2

    return dummy_node.next

Leetcode Day 5: Valid Parentheses Explained

Simona Cancian — Sat, 06 Jul 2024 07:39:28 +0000

The problem is as follows:
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Here is how I solved it:
This is a good example on when to use a stack data structure. We are going to use a stack to keep track of the open brackets and ensure they are closed correctly and in the right order. Let's first figure out what is a stack. Look at this image:

A stack is a Last-In-First-Out (LIFO) data structure, meaning the last element added (pushed) to the stack is the first one to be removed (popped). This makes it ideal for matching parentheses, as we need to ensure that the most recent open bracket is closed by the corresponding close bracket.

Let's step through the logic.

class Solution:
    def isValid(self, s: str) -> bool:
        // my solution here

Create an empty stack to keep track of open brackets.
Create a dictionary to map each type of open bracket to its corresponding close bracket.

stack = []
mapping_parentheses = {"(" : ")", "[" : "]", "{" : "}"}

Loop through each character in the string s.
If the character is an open bracket (i.e., it is a key in the mapping_parentheses dictionary), "push" it onto the stack.
Else if the character is a close bracket, check two conditions:

not stack: If the stack is empty, it means there is no corresponding open bracket for the close bracket, so return False.
char != mapping_parentheses[stack.pop()]: Pop the top element from the stack and check if the popped element matches the current close bracket using the dictionary. If not, return False.

for char in s: 
    if char in mapping_parentheses: 
        stack.append(char)
    elif not stack or char != mapping_parentheses[stack.pop()]:
        return False

After processing all characters, if the stack is empty, it means all open brackets were correctly matched and closed. If the stack is not empty, it means there are unmatched open brackets, so return False.

return not stack

Here is the completed solution:

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping_parentheses = {"(" : ")", "[" : "]", "{" : "}"}

        for char in s: 
            if char in mapping_parentheses: 
                stack.append(char)
            elif not stack or char != mapping_parentheses[stack.pop()]:
                return False
        return not stack

Leetcode Day 5: Valid Parentheses Explained

Simona Cancian — Sat, 06 Jul 2024 07:39:27 +0000

The problem is as follows:
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Let's step through the logic.

class Solution:
    def isValid(self, s: str) -> bool:
        // my solution here

Create an empty stack to keep track of open brackets.
Create a dictionary to map each type of open bracket to its corresponding close bracket.

stack = []
mapping_parentheses = {"(" : ")", "[" : "]", "{" : "}"}

Loop through each character in the string s.
If the character is an open bracket (i.e., it is a key in the mapping_parentheses dictionary), "push" it onto the stack.
Else if the character is a close bracket, check two conditions:

not stack: If the stack is empty, it means there is no corresponding open bracket for the close bracket, so return False.
char != mapping_parentheses[stack.pop()]: Pop the top element from the stack and check if the popped element matches the current close bracket using the dictionary. If not, return False.

for char in s: 
    if char in mapping_parentheses: 
        stack.append(char)
    elif not stack or char != mapping_parentheses[stack.pop()]:
        return False

After processing all characters, if the stack is empty, it means all open brackets were correctly matched and closed. If the stack is not empty, it means there are unmatched open brackets, so return False.

return not stack

Here is the completed solution:

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping_parentheses = {"(" : ")", "[" : "]", "{" : "}"}

        for char in s: 
            if char in mapping_parentheses: 
                stack.append(char)
            elif not stack or char != mapping_parentheses[stack.pop()]:
                return False
        return not stack

Leetcode Day 4: Longest Common Prefix Explained

Simona Cancian — Fri, 05 Jul 2024 05:08:18 +0000

The problem is as follows:
Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Here is how I solved it:

If there input list of strings is empty, it means that there is no common prefix to check so we return an empty string.

if not strs:
    return ""

Use the first string in the list as a reference for comparison

for i in range(len(strs[0])):
    char = strs[0][i]

For each character in the reference string, compare it with the corresponding character in all other strings. If any string has a different character at the same position or is shorter than current position i, it means that the common prefix ends before this character. Therefore, return the substring of the reference string up to this point.

for string in strs[1:]:
    if i >= len(string) or string[i] != char:
        return strs[0][:i]

If loops completes without returning, it means that the reference string itself is the longest common prefix

    return strs[0]

OR just use os standard library available in Python. It includes functions for file and directory manipulation, environment variables, process management etc.
The os module provides a way to interact with the operating system in a portable way.
Here is the completed solution:

import os

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix = os.path.commonprefix(strs)
        return prefix

Leetcode Day 3: Roman to Integer Explained

Simona Cancian — Thu, 04 Jul 2024 04:38:26 +0000

The problem is as follows:
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol: Value
I: 1
V: 5
X: 10
L: 50
C: 100
D: 500
M: 1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900. Given a roman numeral, convert it to an integer.

Here is how I solved it:

Let's make use of a dictionary to map each roman numeral to its integer value.
Initialize a variable result to 0, which we will use to store the final integer value.

roman_numbers = {'I' : 1, 'V' : 5, 'X' : 10, 'L' : 50, 'C' : 100, 'D' : 500, 'M' : 1000}      
result = 0

Iterate through the string.
If current character is greater than previous character, subtract twice the value of "s[char - 1]" and add the value of "s[char]". Here is where we handle the subtraction cases. For example, IV = 4 (I=1 is less than V=5, so add 5 and subtract 1 twice: 5 - 2 + 1.
Else, add the value of "s[char]" to the result. Here is where we handle the regular addition.
Return result, which is the integer value of the roman numeral.

for char in range(len(s)):
    if char > 0 and roman_numbers[s[char]] > roman_numbers[s[char - 1]]:             
        result += roman_numbers[s[char]] - 2 * roman_numbers[s[char - 1]]
    else:
        result += roman_numbers[s[char]]
return result

Here is the completed solution:

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_numbers = {'I' : 1, 'V' : 5, 'X' : 10, 'L' : 50, 'C' : 100, 'D' : 500, 'M' : 1000}      
        result = 0

        for char in range(len(s)):            
            if char > 0 and roman_numbers[s[char]] > roman_numbers[s[char - 1]]:                
                result += roman_numbers[s[char]] - 2 * roman_numbers[s[char - 1]]
            else:               
                result += roman_numbers[s[char]]
        return result

Leetcode Day 2: Palindrome Number Explained

Simona Cancian — Wed, 03 Jul 2024 02:19:12 +0000

The problem is as follows:
Given an integer x, return true if x is a palindrome, and false otherwise.

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore, it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore, it is not a palindrome.

Here is how I solved it:

Let's convert the given integer into a string
In Python we can reverse a string by slicing: create a slice that starts at the end of the string and moves backwards. The slice statement [::-1] means start and end of the string and end at position 0, move with the step -1, which means one step backwards. https://www.w3schools.com/python/python_howto_reverse_string.asp

rev = str(x)[::-1]

Let's compare the reversed string to the given integer (again, convert it to string: we can only compare same datatypes). Return True if it matches, else False.

if rev == str(x):
    return True
return False

But hey, we can actually write just one line of code using ternary operator! To be honest, I am not sure if it's bad design, but it seemed more readable to me.
Here is the complete solution:

class Solution:
    def isPalindrome(self, x: int) -> bool:
        return True if str(x)[::-1] == str(x) else False

Leetcode Day 1: Two Sum Explained

Simona Cancian — Tue, 02 Jul 2024 05:34:12 +0000

The problem is as follow:

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]

Here is how I solved it:

We want to create a dictionary named index_map to store the integers in nums and their corresponding indices.

index_map = {}

Then, we will use enumerate to get both index i and value num of each element in nums. For each integer, let's calculate the complement, which is the difference between the target and the current element num.

for i, num in enumerate(nums):
    n = target - num

Now check the dictionary: if n is in the dictionary, it means we have found the two integers that add up to the target Return the n index and the current index as a list.

if n in index_map: 
    return [index_map[n], i]

Else, if n is not in the dictionary, add the current element num and index to the dictionary.

index_map[num] = i

Here is the completed solution:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        index_map = {}
        for i, num in enumerate(nums):
            n = target - num
            if n in index_map: 
                return [index_map[n], i]
            index_map[num] = i