DEV Community: WhereIsLijah

977. Squares of a Sorted Array

WhereIsLijah — Wed, 14 Aug 2024 16:05:38 +0000

Here we employ 2 pointers to keep track of the indices

Solution:
Since it is in a non-decreasing order e.g [-4,-1,0,3,10], we need to compare values of both pointers and also keep track of the indices after each iteration.

1 - Initialize left pointer to 0, representing the start of the list.
2 - Initialize right pointer to the last index of the list (len(nums) - 1).
3 - Create an empty list result to store the squares of the elements.
4 - Loop while left is less than or equal to right:
4a - Compare the absolute values of the elements at the left and right pointers.
4b - If the absolute value of the element at left is greater than that at right, append the square of the element at left to result, and increment the left pointer by 1.
4c - Else, append the square of the element at right to result, and decrement the right pointer by 1.
5 - After the loop, reverse the result list to ensure the squares are in non-decreasing order.
6 - Return the result list, which now contains the squared values sorted in non-decreasing order.

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left = 0
        right = len(nums)-1
        result = []

        while left <= right:
            if abs(nums[left]) > abs(nums[right]):
                result.append(nums[left] ** 2)
                left +=1
            else:
                result.append(nums[right] ** 2)
                right -=1

        result.reverse()

        return result

20. Valid Parentheses

WhereIsLijah — Mon, 29 Jul 2024 14:28:05 +0000

We must consider that each bracket is closed in the correct order, which is vital logic we must pay attention to for our program to work.

Since this is a stack-based question, an easy way would be to represent our stack as a list and also use a mapping (dictionary) of each closing bracket to their corresponding opening brackets.

Solution:
1 - create an empty stack

2 - create a map that contains key-value pairs with the closing brackets being the key and their corresponding opening brackets being the value

3 - loop through each character in the string
3a - if the character is not Mapped (it means it is an opening bracket) then we append it to the stack and continue to the next character.

4 - else if the character is in the map then we check if the stack is empty (if it is then there's a problem because we have nothing to compare our closing brackets with) or also peek/check the most recent entry(top) into the stack and compare to the value of the current key in the Map, If they are not equal then return False.

5 - if the element matches, we pop the last entry into the stack to move to the next character/bracket.

6 - (Outside the loop) Then we return the length of the stack, if empty then it is valid, else it is invalid

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

    for c in s:
        if c not in Map:
            stack.append(c)
            continue
        elif c in Map:
            if len(stack) == 0 or stack[-1] != Map[c]:
                return False
            stack.pop()
    return len(stack) == 0

Data structures - Stack

WhereIsLijah — Mon, 29 Jul 2024 13:53:47 +0000

Stack, Array, and linked list are linear data structures

Stack operations (LIFO):
1 - Push
2 - Pop
3 - Peek/Top: returns the last element without removing it
4 - Check if the stack is empty -> boolean
5 - Check Size
6 - Check if the stack is full

167. Two Sum II - Input Array Is Sorted

WhereIsLijah — Thu, 25 Jul 2024 03:18:53 +0000

Refer to Two Sum Solution and add +1 to the indices!

125. Valid Palindrome

WhereIsLijah — Wed, 12 Jun 2024 16:43:54 +0000

Topic: Arrays & Hashing

Soln 1 (isalnum):

A not so efficient solution:

create a new list to store the palindrome
loop through the characters in the string:
check if it is alphanumeric, if it is then append to list
assign a variable, then convert palindrome list to string
assign another variable, then reverse palindrome
return and compare both variables

def isPalindrome(self, s: str) -> bool:
    palin = []

    for c in s:
        if c.isalnum():
            palin.append(c.lower())
    x = ''.join(palin)
    y = x[::-1]

    return x == y

Soln 2 (isalnum):

Filter and Normalize: Create palindrome by joining all alphanumeric characters from s and converting them to lowercase.
Check Palindrome: Return True if palindrome is equal to its reverse, otherwise return False.

def isPalindrome(self, s: str) -> bool:
        palindrome = ''.join(filter(str.isalnum, s)).lower()
        return palindrome == palindrome[::-1]

Notes: Attempt to understand 2 pointer solution.

238. Products of Array Discluding Self

WhereIsLijah — Tue, 11 Jun 2024 18:59:50 +0000

Topic: Arrays & Hashing

Soln 1 (prefix & suffix):

Get the length of the input list and create 2 lists (prefix and suffix) and assign 1 to them
Iterate through the input list starting from the second element (index 1) because the first element (index 0) has no elements to its left.
For each element, set the current position in the prefix list to the product of the previous position in the prefix list and the previous element in the original list nums.
Iterate through the input list in reverse order starting from the second-to-last element (index n-2) because the last element (index n-1) has no elements to its right.
For each element, set the current position in the suffix list to the product of the next position in the suffix list and the next element in the original list nums.
return a combined multiplication of both list.

x = len(nums)
prefix = [1] * x
suffix = [1] * x

for index in range(1, x):
    prefix[index] = prefix[index - 1] * nums[index - 1]    

for index in range(x -2, -1, -1):
    suffix[index] = suffix[index+1] * nums[index + 1]   

return [prefix[i] * suffix[i] for i in range(x)]

Soln 2 (prefix & suffix)

Create an array result of the same length as nums, with all elements set to 1.
Initialize prefix to 1, Iterate over nums from left to right, For each element i, set result[i] to prefix and update prefix by multiplying it with nums[i].
Initialize suffix to 1, Iterate over nums from right to left, For each element i, multiply result[i] by suffix and update suffix by multiplying it with nums[i].
Return the result array.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = [1] * len(nums)
        pre = 1

        for i in range(len(nums)):
            result[i] = pre
            pre *= nums[i]
        suf = 1
        for i in range(len(nums) -1, -1, -1):
            result[i] *=suf
            suf *= nums[i]  

        return result

Soln 3:

There is a lazy solution where all you have to do is multiply all the elements in the list to get the total product, e.g using reduce (imported from functool) then divide by the element and return a list of the solution.
The drawback of this is it uses division and it fails when any element in the list is zero.

def productExceptSelf(self, nums: List[int]) -> List[int]:
        total_product = reduce(lambda x, y: x * y, nums)

        result = [total_product // num for num in nums]

        return result

Notes: None

347. Top K Frequent Elements

WhereIsLijah — Tue, 11 Jun 2024 05:22:47 +0000

Topic: Arrays & Hashing

Soln 1 (dictionary + lambda):

Create an empty dictionary
Iterate through the list "nums" with num:
if the key [num] is not in the dictionary, then add to both the key [num] and the value [occurrence] 1 as the first occurence of that key [num]
else it means the key [num] already exists and you need to increment the value [occurrence] in the dictionary
Sort the dictionary items by their values in descending order, extract the keys of the top k items, and return.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq_dict = {}

        for i in nums:
            if i not in freq_dict:
                freq_dict[i] = 1
            else:
                freq_dict[i] +=1

        return [item[0] for item in (sorted(freq_dict.items(), key=lambda item: item[1], reverse=True)[:k])]

Soln 2 (dictionary + lambda):

Create an empty dictionary
iterate through the list "nums" using num:
get the value of num, if it exists, increment by 1, else, assign a default value of 0
Sort the dictionary items by their values in descending order using a lambda function
Return a list of the first k keys from the sorted dictionary.

dic = {}
        for num in nums:
            dic[num] = dic.get(num, 0) + 1

        freq = dict(sorted(dic.items(), key=lambda x: x[1], reverse=True))
        return list(freq.keys())[:k]

Notes:
A lambda is an anonymous function that can be used in place of a normal function. It can take arguments and is often used with higher-order functions.

Syntax: Lambda arguments: expression
e.g

cubed = lambda x: x**3
nums = [1, 2, 3]
cubed_nums = list(map(cubed, nums))
# Output: [1, 8, 27]

Higher-order functions, e.g map, reduce, filter, zip, sorted

49. Group Anagrams

WhereIsLijah — Sun, 09 Jun 2024 05:41:36 +0000

Topic: Arrays & Hashing

Soln 1 (dictionary):

create a dictionary
iterate through the string of wordsa
sort the word alphabetically
if the key[sorted word] is not in the dictionary then add it and use the original word as its value
else append the word to the already existing key

    word_dict = {}

    for word in strs:
        sorted_word = ''.join(sorted(word))

        if sorted_word not in word_dict:
            word_dict[sorted_word] = [word]
        else:
            word_dict[sorted_word].append(word)

    return list(word_dict.values())

Soln 2 (tuples + defaultdict):

Initialize a Dictionary: Create an empty dictionary.
Iterate Through the List of Strings: Loop through each string in the input list.
Sort Each String and Convert to a Tuple: For each string, sort the characters and convert the sorted list to a tuple.
Use Tuple as Key and Append String as Value: Use the tuple as the key in the dictionary. Append the original string to the list corresponding to this key.
Return the Values of the Dictionary: Extract the values from the dictionary which are the groups of anagrams.

from collections import defaultdict

def group_anagrams(strs):
    count = defaultdict(list)

    for i in strs:
        count[tuple(sorted(i))].append(i)

    return count.values()

Note: defaultdict is a sub-class of the dictionary class that returns a dictionary-like object. The functionality of both dictionaries and defaultdict are almost same except for the fact that defaultdict never raises a KeyError. It provides a default value for the key that does not exists.

Tuple is an ordered, immutable collection of elements.

1. Two Sum

WhereIsLijah — Sat, 08 Jun 2024 20:20:12 +0000

Topic: Array & Hashing

Soln 1 (dictonary solution):
After learning how to use dictionaries in the previous leetcode questions, i decided to see how many more solutions i can provide for using it.

Create an empty dictionary to store the key-value pairs (this will be where the values and it's respective indiced will be stored)
loop through the list nums with both the indices and the values:
Initialize a variable (complement); its value will be the result of the target minus the current number [Major logic of the solution] - for every number in the list
if the complement exists in the dictionary, then we return the index of the complement in the dictionary and the current index from the loop we are iterating with.
else we add this complement into our dictionary (both key and value) which means

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_index = {}

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

            if complement in num_index:
                return [num_index[complement], i]
            else:
                num_index[nums[i]] = i

Soln 2 (Bruteforce):

iterate through the list using index i (outer loop)
iterate through the list using index j starting from (i + j) to avoid duplicates (inner loop)
compare the sum of both elements at indices i and j to the target
if the sum is equal to the target then return the indices [i, j]

for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        if nums[i] + nums[j] == target:
            return([i, j])

Note: Hashmaps use key-value pairs, try to solve questions with methods you know before trying to improve them.

242. Valid Anagram

WhereIsLijah — Fri, 07 Jun 2024 16:31:46 +0000

Topic: Array & Hashing

Soln 1 (dictonary solution):

Compare the lengths of both strings.
If they are not the same length, they are not anagrams.
Create a new dictionary called count.
Loop through the characters in s:
If the character already exists in the dictionary, then increment its value by 1.
Else, assign the value of the key to 1.
Loop through the characters in t:
If the character does not exist in the dictionary or the character count is 0, then return False.
Else, decrement the value of the character by 1.
Return True.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        count = {}

        for char in s:
            if char in count:
                count[char]+=1
            else:
                count[char] = 1

        for char in t:
            if char not in count or count[char] == 0:
                return False
            count[char]-=1
        return True

Soln 2 (set solution):

Compare the lengths of both strings.
If they are not the same length, they are not anagrams.
Loop through the characters in the set of s (set removes the duplicates):
If the count of any character in s is not equal to the count of the same character in t:
then return False.
If all character counts match, then the strings are anagrams (return True).

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False 
        for i in set(s): 
            if s.count(i) != t.count(i):
                return False
        return True

Soln 3:
A very obvious solution:

Alphabetically sort both strings (s, t) and compare them. Returns True if they both are the same length and contain the same characters, else False if they do not. (Yes, all on the same line.)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

Notes:
Sets & dictionaries are unordered and unique, although dictionaries can contain duplicates values

217. Contains Duplicate

WhereIsLijah — Fri, 07 Jun 2024 06:09:59 +0000

Topic: Array & Hashing

I came up with 2 different solutions

Soln 1:

Compare the length of the array with the length of the set created from the array
Sets is a data structure that does not contain duplicates elements

return len(nums) != len(set(nums))

Soln 2:

Declare a set as a variable
loop through the integers in the array
if the integer does not exist in the set, add it to the set
else, it means a duplicate exists

         count = set()

         for n in nums:
             if n in count:
               return True
             count.add(n)

         return False

Notes: I worked on this before and just needed it to re-introduce myself into leetcoding

Leetcode accountability yet again...

WhereIsLijah — Fri, 07 Jun 2024 04:13:05 +0000

One thing I have struggled with in recent months is leetcoding, Due to a lack of accountability, I solve a few questions and then just forget about doing them. I know most developers do them for the sole purpose of interviewing, but I guess I primarily want to do this to get better at solving problems.

I'm restarting with Neetcode 150 questions, 1 question a day, due to other life activities, and the moment i get sucked back in i'll increase the number of daily questions i solve.

I'll be solving all questions in Python