Skip to content

Commit 057eaec

Browse files
author
Мето Трајковски
committed
New solutions
1 parent c5374f2 commit 057eaec

File tree

5 files changed

+313
-0
lines changed

5 files changed

+313
-0
lines changed

‎Lists/find_first_missing_positive.py‎

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
'''
2+
Find first missing positive integer (>0)
3+
4+
Given an array of integers, find the first missing positive integer in linear time and constant space.
5+
In other words, find the lowest positive integer that does not exist in the array.
6+
The array can contain duplicates and negative numbers as well.
7+
Note: you can modify the input array in-place.
8+
9+
Input: [3, 4, -1, 1]
10+
Output: 2
11+
12+
Input: [1, 2, 0]
13+
Output: 3
14+
15+
=========================================
16+
Play with indicies and mark them, a marked index means that the number equals to that index exist in the array.
17+
Time Complexity: O(N)
18+
Space Complexity: O(1)
19+
'''
20+
21+
22+
############
23+
# Solution #
24+
############
25+
26+
def find_first_missing(a):
27+
n = len(a)
28+
29+
# eliminate all zeros and all negative numbers
30+
for i in range(n):
31+
if a[i] < 1:
32+
a[i] = n + 1 # those elements aren't used later
33+
34+
# find all numbers in the range and mark all numbers at those positions as negative numbers
35+
for i in range(len(a)):
36+
idx = abs(a[i]) - 1
37+
if idx >= n:
38+
continue
39+
val = a[idx]
40+
41+
if val > 0:
42+
# mark element as found for the first time
43+
a[idx] = -val
44+
45+
# find the first non-negative position
46+
for i in range(n):
47+
if a[i] > 0:
48+
return i + 1
49+
50+
return n + 1
51+
52+
53+
###########
54+
# Testing #
55+
###########
56+
57+
# Test 1
58+
# Correct result => 1
59+
test = [-1, 2, 3]
60+
print(find_first_missing(test))
61+
62+
# Test 2
63+
# Correct result => 2
64+
test = [3, 4, -1, 1] # 2
65+
print(find_first_missing(test))
66+
67+
# Test 3
68+
# Correct result => 3
69+
test = [1, 2, 0] # 3
70+
print(find_first_missing(test))
71+
72+
# Test 4
73+
# Correct result => 4
74+
test = [1, 2, 3]
75+
print(find_first_missing(test))
76+
77+
# Test 5
78+
# Correct result => 5
79+
test = [-4, -1, -3, -1]
80+
print(find_first_missing(test))
81+
82+
# Test 6
83+
# Correct result => 6
84+
test = [2, 1, 2, -1, 0, 20]
85+
print(find_first_missing(test))
86+
87+
# Test 7
88+
# Correct result => 7
89+
test = [1, 2, 5, 5, 1, 2]
90+
print(find_first_missing(test))

‎Lists/find_one_missing_number.py‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
'''
2+
Find the missing number in a sequence
3+
4+
Find the only missing integer in a sequence,
5+
all numbers are integers and they're smaller or equal to N+1 (N is length of the array).
6+
7+
Input: [2, 1, 4]
8+
Output: 3
9+
10+
=========================================
11+
Searching for 1 unknown, math problem.
12+
Use the sum formula for the first N numbers to compute the whole sum of the sequence.
13+
After that sum all elements from the array, and when you subtract those 2 numbers, you'll get the missing number.
14+
Sum formula = N*(N+1)/2
15+
Time Complexity: O(N)
16+
Space Complexity: O(1)
17+
'''
18+
19+
############
20+
# Solution #
21+
############
22+
23+
def missing_number(nums):
24+
s = sum(nums)
25+
n = len(nums) + 1
26+
# sum formula (sum of the first n numbers) = (N*(N+1))/2
27+
return n * (n + 1) // 2 - s
28+
29+
30+
###########
31+
# Testing #
32+
###########
33+
34+
# Test 1
35+
# Correct result => 4
36+
print(missing_number([2, 3, 1]))
37+
38+
# Test 2
39+
# Correct result => 3
40+
print(missing_number([2, 1, 4]))

‎Lists/find_two_missing_numbers.py‎

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
'''
2+
Find two missing numbers in a sequence
3+
4+
Find two missing numbers in a sequence,
5+
all numbers are integers and they're smaller or equal to N+2 (N is length of the array).
6+
7+
Input: [2, 1, 4]
8+
Output: [3, 5]
9+
10+
=========================================
11+
Searching for 2 unknowns, math problem.
12+
This solution is extension of 'find_one_missing_number.py'.
13+
But in this case we also need the sum formula for the first squared N numbers (1^2 + 2^2 + ... + N^2).
14+
And using those 2 formulas, we'll solve equations with 2 unknowns.
15+
a + b = diff_sum (diff_sum = formula_sum + list_sum)
16+
a^2 + b^2 = diff_squared_sum (diff_squared_sum = formula_squared_sum + list_squared_sum)
17+
But in the end we'll need quadratic formula to find those values.
18+
b1,2 = (diff_sum +- sqrt(2*diff_squared_sum - diff_sum^2)) / 2
19+
Sum formula = N*(N+1)/2
20+
Squared sum formula = N*(N+1)*(2*N+1)/6
21+
Time Complexity: O(N)
22+
Space Complexity: O(1)
23+
24+
Note: this idea also could be used when more than 2 numbers are missing,
25+
but you'll need more computations/equations, because you'll have K unknowns.
26+
'''
27+
28+
############
29+
# Solution #
30+
############
31+
32+
import math
33+
34+
def missing_numbers(nums):
35+
# find sums from the array
36+
s = 0
37+
s_2 = 0
38+
for i in nums:
39+
s += i
40+
s_2 += i * i
41+
42+
n = len(nums) + 2
43+
44+
# using formulas, compute the sums of the sequence
45+
f_s = n * (n + 1) // 2
46+
f_s_2 = n * (n + 1) * (2 * n + 1) // 6
47+
48+
# difference of sums
49+
d = f_s - s
50+
d_2 = f_s_2 - s_2
51+
52+
# using quadratic formula find the values
53+
r = int(math.sqrt(2 * d_2 - d * d))
54+
55+
a = (d - r) // 2
56+
b = (d + r) // 2
57+
58+
return [a, b]
59+
60+
61+
###########
62+
# Testing #
63+
###########
64+
65+
# Test 1
66+
# Correct result => [4, 5]
67+
print(missing_numbers([2, 3, 1]))
68+
69+
# Test 2
70+
# Correct result => [1, 2]
71+
print(missing_numbers([5, 3, 4]))
72+
73+
# Test 3
74+
# Correct result => [1, 5]
75+
print(missing_numbers([2, 3, 4]))

‎README.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -54,20 +54,24 @@ Solution 2 explanation
5454
############
5555
# Solution #
5656
############
57+
5758
def name_of_problem(params):
5859
# description of code
5960
pass
6061

6162
##############
6263
# Solution 2 #
6364
##############
65+
6466
def name_of_problem_2(params):
6567
# description of code
6668
pass
6769

70+
6871
###########
6972
# Testing #
7073
###########
74+
7175
# Test 1
7276
# Correct result => 'result'
7377
print(name_of_problem('example'))

‎Trees/valid_bst.py‎

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
'''
2+
Valid binary search tree
3+
4+
Check if a given tree is a valid binary search tree.
5+
6+
Input: 5
7+
/ \
8+
1 7
9+
/ \
10+
6 8
11+
Output: True
12+
13+
=========================================
14+
Visit all nodes and check if the values are inside the boundaries.
15+
When visiting the left child use the value of the parent node like an upper boundary.
16+
When visiting the right child use the value of the parent node like a lower boundary.
17+
Time Complexity: O(N)
18+
Space Complexity: O(N) - (recursion is used, this complexity is because of stack)
19+
'''
20+
21+
############
22+
# Solution #
23+
############
24+
25+
import math
26+
27+
class TreeNode:
28+
def __init__(self, val, left=None, right=None):
29+
self.val = val
30+
self.left = left
31+
self.right = right
32+
33+
def is_valid_bst(root):
34+
return is_valid_sub_bst(root, -math.inf, math.inf)
35+
36+
def is_valid_sub_bst(node, lower, upper):
37+
if node is None:
38+
return True
39+
40+
if (node.val <= lower) or (node.val >= upper):
41+
return False
42+
43+
# check left
44+
if not is_valid_sub_bst(node.left, lower, node.val):
45+
return False
46+
47+
# check right
48+
if not is_valid_sub_bst(node.right, node.val, upper):
49+
return False
50+
51+
return True
52+
53+
54+
###########
55+
# Testing #
56+
###########
57+
58+
# Test 1
59+
'''
60+
5
61+
/ \
62+
1 4
63+
/ \
64+
3 6
65+
'''
66+
# Correct result => False
67+
root = TreeNode(5, TreeNode(1), TreeNode(4, TreeNode(3), TreeNode(6)))
68+
print(is_valid_bst(root))
69+
70+
# Test 2
71+
'''
72+
5
73+
/ \
74+
1 6
75+
/ \
76+
4 7
77+
'''
78+
# Correct result => False
79+
root = TreeNode(5, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7)))
80+
print(is_valid_bst(root))
81+
82+
# Test 3
83+
'''
84+
5
85+
/ \
86+
1 6
87+
/ \
88+
7 8
89+
'''
90+
# Correct result => False
91+
root = TreeNode(5, TreeNode(1), TreeNode(6, TreeNode(7), TreeNode(8)))
92+
print(is_valid_bst(root))
93+
94+
# Test 4
95+
'''
96+
5
97+
/ \
98+
1 7
99+
/ \
100+
6 8
101+
'''
102+
# Correct result => True
103+
root = TreeNode(5, TreeNode(1), TreeNode(7, TreeNode(6), TreeNode(8)))
104+
print(is_valid_bst(root))

0 commit comments

Comments
 (0)