LeetCode Solutions
LeetCode Solutions | Leetcode Questions
Knowledge Center
1 / 252
https://www.youtube.com/watch?v=VbVQJRKXxBA&list=PL1w8k37X_6L86f3PUUVFoGYXvZiZHde1S&index=2
=========================================
Solving LeetCode problems.
1. Two Sum
Easy
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]
Constraints:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
Solution:
1. Brute force method:
Complexity Analysis
Time complexity: O(n^2)
For each element, we try to find its complement by looping through the rest of the array. Therefore, the time complexity is O(n^2).
Space complexity: The space required does not depend on the size of the input array, so only constant space is used.
2. Insert the list elements into a dict which is a Python hashtable. Loop through the list and determine if the dict holds a complement (target - nums[i]target.
Avoid nested for loops and use a dist instead. Sets also test for member in constant time.
9. Palindrome Number
Given an integer x, return true if x is palindrome integer.
An integer is a palindrome when it reads the same backward as forward.
For example, 121 is a palindrome while 123 is not.
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.
Constraints:
-231 <= x <= 231 - 1
Follow up: Could you solve it without converting the integer to a string?
Solution:
1. Construct from the integer input a new reversed string s.reversed. Test the original string and reversed == If True then the input is a numeric palindrome.
2. Solve it without converting the integer to a string:
Copy the integer for later comparison. Use the modulus operator to divide the number by 10 to get the remainder. Append the value of the remainder by adding it to a new number named palindrome.
# floor divide the number leave out the last digit from number
number=number//10
13. Roman Number to Integer
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 one's 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.
Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.
Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Constraints:
1 <= s.length <= 15
s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
It is guaranteed that s is a valid roman numeral in the range [1, 3999].
Solution:
Roman numeral (n) Decimal value (v)
I 1
IV 4
V 5
IX 9
X 10
XL 40
L 50
XC 90
C 100
CD 400
D 500
CM 900
M 1000
Loop through the input integer s starting 1 or 2 characters from left to right. After matching each Roman numeral delete the underlying integer from the original input.
14. Longest Common Prefix
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 "".
Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Solution:
Longest Common Prefix Solving with 10+ Methods using Python
def longestCommonPrefix(strs):
longest_pre = ""
if not strs: return longest_pre
shortest_str = min(strs, key=len)
for i in range(len(shortest_str)):
if all([x.startswith(shortest_str[:i+1]) for x in strs]):
longest_pre = shortest_str[:i+1]
else:
break
# print longest_pre()
return(longest_pre)
strs = ["carry", "cart", "carbon"]
longestCommonPrefix(strs)
output: 'car'
Notes:
strs is a list containing 3 strings. Find the shortest length string using the min function. The longest common prefix cannot be longer than the length of the shortest string.
Set up a for i in range loop the size of the shortest string.
Use the built-in function all to test the truth of the slice of all strings in strs string starting and incrementing from the right side of each string.
20. Valid Parentheses
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.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Constraints:
1 <= s.length <= 104
s consists of parentheses only '()[]{}'.
Solution:
https://redquark.org/leetcode/0020-valid-parentheses/
def isValid(s: str) -> bool:
# Stack for left symbols
leftSymbols = []
# Loop for each character of the string
for c in s:
# If left symbol is encountered
if c in ['(', '{', '[']:
leftSymbols.append(c)
# If right symbol is encountered
elif c == ')' and len(leftSymbols) != 0 and leftSymbols[-1] == '(':
leftSymbols.pop()
elif c == '}' and len(leftSymbols) != 0 and leftSymbols[-1] == '{':
leftSymbols.pop()
elif c == ']' and len(leftSymbols) != 0 and leftSymbols[-1] == '[':
leftSymbols.pop()
# If none of the valid symbols is encountered
else:
return False
return leftSymbols == []
Notes:
leftSymbols is a list with members ['(', '{', '[']
for c in s if left symbol is encountered then leftSymbols.append(c)
This approach uses leftSymbols with append as a stack push operation.
21. Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a 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]
Constraints:
The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.
Solutions:
My first inclination is to convert the linked lists to lists then merge them using the zip function.
Merge two sorted linked lists into one, techie delight
https://www.techiedelight.com/merge-given-sorted-linked-lists/
LeetCode #21 - Merge Two Sorted Lists, red quark
https://redquark.org/leetcode/0021-merge-two-sorted-lists/
Merge two sorted lists (in-place), GeeksforGeeks
https://www.geeksforgeeks.org/merge-two-sorted-lists-place/
Convert a Singly Linked List to an array, GeeksforGeeks
https://www.geeksforgeeks.org/convert-a-singly-linked-list-to-an-array/
Convert a Singly Linked List to an Array in Python, CodeSpeedy
https://www.codespeedy.com/convert-a-singly-linked-list-to-an-array-in-python/
26. Remove Duplicates from Sorted Array
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.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
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).
Constraints:
1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.
Solutions
https://redquark.org/leetcode/0026-remove-duplicates-from-sorted-array/
class RemoveDuplicatesFromSortedArray:
def removeDuplicates(self, nums: List[int]) -> int:
# Length of the update array
count = 0
# Loop for all the elements in the array
for i in range(len(nums)):
# If the current element is equal to the next element, we skip
if i < len(nums) - 2 and nums[i] == nums[i + 1]:
continue
# We will update the array in place
nums[count] = nums[i]
count += 1
return count
https://www.techiedelight.com/remove-duplicates-sorted-linked-list/
LeetCode Solutions | Leetcode Questions
Knowledge Center
1 / 252
https://www.youtube.com/watch?v=VbVQJRKXxBA&list=PL1w8k37X_6L86f3PUUVFoGYXvZiZHde1S&index=1