LeetCode Flashcards
Contains Duplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Brute force:
compare each element with other elements to check if there Is any duplicates, O(N^2) where ‘N’ number of element in the array.
spring and check each neighbour elements. O(N log N)
#for num in nums
#if nums in hashSet -> return true
#if nums not in hashSet -> add num to hashset
#retutrn false
Valid Anagram
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once
check len s == len t
#Brue force
#sort how to sort a string
#two pointers better -> .equal()
#O(N log N)
#better
#hashmap, we could use array because we have just 26 letters, then ord(char) - ord('a')
#two pointers better -> .equal()
#complexity O(N), space O(1) 26 chars
Two Sum:
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.
”””
brue force:
check the sum of each element sum if it’s equal to the target
time complixity: O(N^2)
space complixity: O(1)
n = the number of the element in the array.
“””
“””
hash table approch:
loop over the array,
- add to the hash map complement - element
loop over the array,
- check if complement -element is exist if yes return it’s index and the index in the hashmap.
time complixity: O(N)
space complixity: O(N)
n = the number of the element in the array
“””
“””
better aproch (optimized):
- check in hashmap if complement - elemet exists: if yes reutrn else add complement - element in same loop
time complixity: O(N)
space complixity: O(N)
n = the number of the element in the array
“””
Group Anagrams
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
loop over the strings
#sort the word
#if it's sortion exists in mp -> add the word to the value of the sorted word.
#else init the sorted word with the word value.
#loop over the values of the map and append them into array
Product of Array Except Self
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
pre array which contains the calculation of products of the prev
post array which contains the calculation of products of post
then multiply each other.
O(N) time,
O(N) or O(1) according of how you implement it.
Encode and Decode Strings
Problem: Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings. Please implement encode and decode
ically, one of the easy solution is to define a delimiter which could be any special character like # or / to separate words in encode method. However, this special character might appear in the word in real world. We can get around it by appending an escaped character or size of the word. Here, we append the size of the word when encoding
Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
hash set contains all the nums,
counter and max,
for each number check if the num - 1 is in the hash set, if yes counter +1
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.
Return true if there is a cycle in the linked list. Otherwise, return false.
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow,fast = head,head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False time: O(N) space: O(1)
Merge Two Sorted Lists
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
res = runner = ListNode()
while list1 and list2:
if list1.val < list2.val:
runner.next = list1
list1 = list1.next
else:
runner.next = list2
list2 = list2.next
runner = runner.next
if list1 or list2:
runner.next = list1 if list1 else list2
return res.next O(n+m) O(1)
- Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
res = ListNode()
dump = res
tens = 0
while l1 and l2:
sum_two_nums = l1.val + l2.val + tens
ones = sum_two_nums % 10
tens = sum_two_nums // 10
res.next = ListNode(val = ones)
res = res.next
l1 = l1.next
l2 = l2.next
while l1:
ones = (l1.val + tens) % 10
tens = (l1.val + tens) // 10
res.next = ListNode(val = ones)
res = res.next
l1 = l1.next
while l2:
ones = (l2.val + tens) % 10
tens = (l2.val + tens) // 10
res.next = ListNode(val = ones)
res = res.next
l2 = l2.next
if tens != 0:
res.next = ListNode(val = tens)
return dump.next
