Skip to content

Commit 8975495

Browse files
author
Мето Трајковски
committed
Added new solutions
1 parent 77d9755 commit 8975495

8 files changed

Lines changed: 559 additions & 10 deletions

‎Backtracking/find_min_path.py‎

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
'''
2+
Find min path
3+
4+
You are given an M by N matrix consisting of booleans that represents a board.
5+
Each True boolean represents a wall. Each False boolean represents a tile you can walk on.
6+
Given this matrix, a start coordinate, and an end coordinate,
7+
return the minimum number of steps required to reach the end coordinate from the start.
8+
If there is no possible path, then return null. You can move up, left, down, and right.
9+
You cannot move through walls. You cannot wrap around the edges of the board.
10+
11+
Input:
12+
[[f, f, f, f],
13+
[t, t, f, t],
14+
[f, f, f, f],
15+
[f, f, f, f]]
16+
start = (3, 0)
17+
end = (0, 0)
18+
Output: 7
19+
Output explanation: Starting bottom left and ending top left,
20+
the minimum number of steps required to reach the end is 7,
21+
since we would need to go through (1, 2) because there is a wall everywhere else on the second row.
22+
23+
=========================================
24+
BFS solution using queue.
25+
Time Complexity: O(N * M)
26+
Space Complexity: O(N * M)
27+
'''
28+
29+
30+
############
31+
# Solution #
32+
############
33+
34+
from collections import deque
35+
36+
def find_min_path(board, start, end):
37+
n = len(board)
38+
m = len(board[0])
39+
40+
# create a visited array
41+
visited = []
42+
for row in range(n):
43+
visited.append([])
44+
for el in range(m):
45+
visited[row].append(False)
46+
47+
queue = deque()
48+
queue.append((start, 0))
49+
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)] # up, right, down, left
50+
51+
# simple bfs
52+
while queue:
53+
el = queue.popleft()
54+
position = el[0]
55+
steps = el[1]
56+
57+
# check if this position is already visited
58+
if visited[position[0]][position[1]]:
59+
continue
60+
61+
visited[position[0]][position[1]] = True
62+
63+
# check if this position is walkable
64+
if board[position[0]][position[1]] == 't':
65+
continue
66+
67+
# if the end was reached return steps
68+
if position == end:
69+
return steps
70+
71+
newSteps = steps + 1
72+
73+
# add all neighbours at the end of the queue
74+
for d in directions:
75+
x = position[0] + d[0]
76+
y = position[1] + d[1]
77+
78+
if (x < n) and (x >= 0) and (y < m) and (y >= 0):
79+
queue.append(((x, y), newSteps))
80+
81+
# the path was not found
82+
return None
83+
84+
85+
###########
86+
# Testing #
87+
###########
88+
89+
# Test 1
90+
# Correct result => 7
91+
f = 'f'
92+
t = 't'
93+
print(find_min_path([[f, f, f, f], [t, t, f, t], [f, f, f, f], [f, f, f, f]], (3, 0), (0, 0)))

‎Lists/find_duplicates.py‎

Lines changed: 43 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -10,39 +10,72 @@
1010
mark the value on that position as negative when the element is found for the first time.
1111
Time Complexity: O(N)
1212
Space Complexity: O(D) , array (in this case set) to save all duplicates
13+
In the second solution 2 hashsets are used, one to check if already exists element like current and
14+
the other has same functionality as the hashset in the first solution.
15+
* This solution is for all kind of numbers
16+
(not as the previous solution, only for positive numbers or smaller elements than the length of array).
17+
Time Complexity: O(N)
18+
Space Complexity: O(D)
1319
'''
1420

1521

16-
############
17-
# Solution #
18-
############
22+
##############
23+
# Solution 1 #
24+
##############
1925

20-
def find_duplicates(a):
21-
n = len(a)
26+
def find_duplicates(arr):
27+
n = len(arr)
2228
duplicates = set()
2329

24-
for i in range(len(a)):
25-
idx = abs(a[i]) - 1
26-
val = a[idx]
30+
for i in range(n):
31+
idx = abs(arr[i]) - 1
32+
val = arr[idx]
2733

2834
if val > 0:
2935
# mark element as found for the first time
30-
a[idx] = -val
36+
arr[idx] = -val
3137
else:
3238
# this element is a duplicate
3339
duplicates.add(idx + 1)
3440

3541
return duplicates
3642

3743

44+
##############
45+
# Solution 2 #
46+
##############
47+
48+
def find_duplicates_2(arr):
49+
n = len(arr)
50+
duplicates = set()
51+
elements = set()
52+
53+
for i in range(n):
54+
if arr[i] in duplicates:
55+
# this element is already found as duplicate
56+
continue
57+
58+
if arr[i] in elements:
59+
# a duplicate is found
60+
duplicates.add(arr[i])
61+
elements.remove(arr[i])
62+
else:
63+
# a new number
64+
elements.add(arr[i])
65+
66+
return duplicates
67+
68+
3869
###########
3970
# Testing #
4071
###########
4172

4273
# Test 1
4374
# Correct result => [1]
4475
print(find_duplicates([1, 1, 1, 1]))
76+
print(find_duplicates_2([1, 1, 1, 1]))
4577

4678
# Test 2
4779
# Correct result => [4, 2]
48-
print(find_duplicates([4, 2, 4, 2, 1, 4]))
80+
print(find_duplicates([4, 2, 4, 2, 1, 4]))
81+
print(find_duplicates_2([4, 2, 4, 2, 1, 4]))

‎Lists/find_missing_number_in_second_array.py‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
'''
2+
Find missing number in second array
3+
4+
Given 2 arrays, first array with N elements and second array with N-1 elements.
5+
All elements from the first array exist in the second array, except one. Find the missing number.
6+
7+
Sample input: [1, 2, 3, 4, 5], [1, 2, 3, 4]
8+
Sample output: 5
9+
10+
Sample input: [2131, 2122221, 64565, 33333333, 994188129, 865342234],
11+
[994188129, 2122221, 865342234, 2131, 64565]
12+
Sample output: 33333333
13+
14+
=========================================
15+
The simplest solution is to substract the sum of the second array from the sum of the first array:
16+
missing_number = sum(arr1) - sum(arr2)
17+
But what if we have milions of elements and all elements are with 8-9 digits values?
18+
In this case we'll need to use modulo operation. Make two sums, the first one from MODULO of each element
19+
and the second one from the DIVIDE of each element. In the end use these 2 sums to compute the missing number.
20+
Time Complexity: O(N)
21+
Space Complexity: O(1)
22+
The second solution is XOR soulution, make XOR to each element from the both arrays (same as find_unpaired.py).
23+
Time Complexity: O(N)
24+
Space Complexity: O(1)
25+
'''
26+
27+
28+
##############
29+
# Solution 1 #
30+
##############
31+
32+
def find_missing_number(arr1, arr2):
33+
n = len(arr2)
34+
mod = 10000 # this can be every number, this should be true max_length * mod < max_integer
35+
sum_diff = 0
36+
mod_diff = 0
37+
i = 0
38+
39+
while i < n:
40+
# this is in case if we have too big numbers and to big arrays
41+
sum_diff += arr1[i] % mod - arr2[i] % mod
42+
mod_diff += arr1[i] // mod - arr2[i] // mod
43+
i += 1
44+
45+
# don't forget the last element from the first array!
46+
sum_diff += arr1[n] % mod
47+
mod_diff += arr1[n] // mod
48+
49+
return mod * mod_diff + sum_diff
50+
51+
52+
##############
53+
# Solution 2 #
54+
##############
55+
56+
def find_missing_number_2(arr1, arr2):
57+
n = len(arr2)
58+
missing = 0
59+
i = 0
60+
61+
while i < n:
62+
missing ^= arr1[i] ^ arr2[i]
63+
i += 1
64+
65+
# don't forget the last element from the first array!
66+
missing ^= arr1[n]
67+
68+
return missing
69+
70+
71+
###########
72+
# Testing #
73+
###########
74+
75+
# Test 1
76+
# Correct result => 33333333
77+
arr1 = [2131, 2122221, 64565, 33333333, 994188129, 865342234]
78+
arr2 = [994188129, 2122221, 865342234, 2131, 64565]
79+
print(find_missing_number(arr1, arr2))
80+
print(find_missing_number_2(arr1, arr2))
81+
82+
# Test 2
83+
# Correct result => 5
84+
arr1 = [1, 2, 3, 4, 5]
85+
arr2 = [1, 2, 3, 4]
86+
print(find_missing_number(arr1, arr2))
87+
print(find_missing_number_2(arr1, arr2))

‎Lists/find_unpaired.py‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
'''
2+
Find unpaired element
3+
4+
Given an array with odd number of elements, where (N - 1)/2 elements have duplicates and ONLY 1 is unique.
5+
6+
Input: [1, 5, 3, 1, 5]
7+
Output: 3
8+
9+
=========================================
10+
Using XOR find the unique element.
11+
* Example: 13 XOR 13 = 1101 XOR 1101 = 0.
12+
Time Complexity: O(N)
13+
Space Complexity: O(1)
14+
'''
15+
16+
17+
############
18+
# Solution #
19+
############
20+
21+
def find_unpaired_element(arr):
22+
unique = 0
23+
24+
for el in arr:
25+
unique ^= el
26+
27+
return unique
28+
29+
30+
###########
31+
# Testing #
32+
###########
33+
34+
# Test 1
35+
# Correct result => 3
36+
print(find_unpaired_element([1, 5, 3, 1, 5]))

‎Lists/k_closest_points.py‎

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
'''
2+
K Closest Points
3+
4+
Given an array with points, and another one point. Find the closest K points of the array to the given point.
5+
6+
Input: [(0, 1), (2, 1), (3, 3), (1, 2)], (2, 2), 2
7+
Output: [(2, 1), (1, 2)]
8+
9+
=========================================
10+
Same solution as the nth_smallest.py, in this case we're looking for the K smallest DISTANCES.
11+
Based on the quick sort algorithm (pivoting, divide and conquer).
12+
More precisly in-place quick sort (without using additional space).
13+
Time Complexity: O(N) , O(N + N/2 + N/4 + N/8 + ... + 1 = 2*N = N)
14+
Space Complexity: O(K) , length of the output array
15+
'''
16+
17+
18+
############
19+
# Solution #
20+
############
21+
22+
def find_k_closes(arr, pt, k):
23+
n = len(arr)
24+
if k > n:
25+
return None
26+
if k < 1:
27+
return None
28+
29+
kth_closest(arr, k - 1, 0, n - 1, pt)
30+
31+
return arr[:k]
32+
33+
def kth_closest(arr, n, left, right, pt):
34+
pivot = pivoting(arr, left, right, pt)
35+
36+
if pivot > n:
37+
kth_closest(arr, n, left, pivot - 1, pt)
38+
elif pivot < n:
39+
kth_closest(arr, n, pivot + 1, right, pt)
40+
41+
def pivoting(arr, left, right, pt):
42+
# O(N) pivoting
43+
# takes the last element as pivot
44+
pivot_dist = sqr_dist(pt, arr[right])
45+
new_pivot = left
46+
47+
# iterate the whole array (without the last element)
48+
# and put all elements closer than the pivot (last element) in the first K spots
49+
# with the new_pivot we're "counting" how many closer elements are there
50+
for j in range(left, right):
51+
if sqr_dist(pt, arr[j]) < pivot_dist:
52+
swap(arr, new_pivot, j)
53+
new_pivot += 1
54+
55+
# swap the last (pivot) element with the new_pivot position
56+
swap(arr, new_pivot, right)
57+
58+
# return the new pivot
59+
return new_pivot
60+
61+
def swap(arr, i, j):
62+
# swaps two elements in an array
63+
temp = arr[i]
64+
arr[i] = arr[j]
65+
arr[j] = temp
66+
67+
def sqr_dist(a, b):
68+
# no need from the square root
69+
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
70+
71+
72+
73+
###########
74+
# Testing #
75+
###########
76+
77+
# Test 1
78+
# Correct result => [(2, 2), (2, 1.5), (2, 1)]
79+
print(find_k_closes([(0, 1), (3, 3), (1, 2), (2, 1.5), (3, -1), (2, 1), (4, 3), (5, 1), (-1, 2), (2, 2)], (2, 2), 3))
80+
81+
# Test 2
82+
# Correct result => [(1, 2), (2, 1)]
83+
print(find_k_closes([(0, 1), (2, 1), (3, 3), (1, 2)], (2, 2), 2))

0 commit comments

Comments
 (0)