Updated broken links from the resources, and updated several solutions

MTrajK · MTrajK · commit 6c1975267cbc · 2022-10-23T00:07:38.000+02:00
diff --git a/Arrays/find_el_smaller_left_bigger_right.py b/Arrays/find_el_smaller_left_bigger_right.py
@@ -1,56 +1,67 @@
 '''
 Find the element before which all the elements are smaller than it, and after which all are greater
 
-Given an array, find an element before which all elements are smaller than it, and after which all are greater than it.
-Return the index of the element if there is such an element, otherwise, return -1.
+Given an unsorted array of size N. Find the first element in array such that all of its left elements are smaller and all right elements to it are greater than it.
+Note: Left and right side elements can be equal to required element. And extreme elements cannot be required element.
 
 Input: [5, 1, 4, 3, 6, 8, 10, 7, 9]
-Output: 4
+Output: 6
 
 =========================================
-Traverse the array starting from left and find all max elements till that element.
-Also traverse the array starting from right and find all min elements till that element.
-In the end only compare mins and maxs with the curent element.
+Traverse the array starting and check if the current element is smaller than the wanted one. If it's smaller then reset the result.
+In meantime keep track of the maximum value till the current position. This maximum value will be used for finding a new "middle" element.
+If the maximum value
     Time Complexity:    O(N)
-    Space Complexity:   O(N)
+    Space Complexity:   O(1)
 '''
 
 
 ############
 # Solution #
 ############
 
-import math
-
 def find_element_smaller_left_bigger_right(arr):
     n = len(arr)
-    left_maxs = [-math.inf]
-    right_min = math.inf
-
-    # find all mins from the front
-    for i in range(n - 1):
-        left_maxs.append(max(left_maxs[-1], arr[i]))
+    curr_max = arr[0]
+    result = -1
 
-    for i in range(n - 1, -1, -1):
-        # check if all left are smaller
-        # and all right are bigger
-        if (left_maxs[i] < arr[i]) and (right_min > arr[i]):
-            return i
+    for i in range(1, n):
+        curr_el = arr[i]
 
-        # don't need a separate for loop for this as mins
-        right_min = min(right_min, arr[i])
+        if result == -1 and curr_el >= curr_max and i != n - 1:
+            result = curr_el
+        elif curr_el < result:
+            result = -1
 
-    return -1
+        if curr_el > curr_max:
+            curr_max = curr_el
 
+    return result
 
 ###########
 # Testing #
 ###########
 
 # Test 1
-# Correct result => 4
+# Correct result => 6
 print(find_element_smaller_left_bigger_right([5, 1, 4, 3, 6, 8, 10, 7, 9]))
 
 # Test 2
 # Correct result => -1
-print(find_element_smaller_left_bigger_right([5, 1, 4, 4]))
+print(find_element_smaller_left_bigger_right([5, 1, 4, 4]))
+
+# Test 3
+# Correct result => 7
+print(find_element_smaller_left_bigger_right([5, 1, 4, 6, 4, 7, 14, 8, 19]))
+
+# Test 4
+# Correct result => 5
+print(find_element_smaller_left_bigger_right([4, 2, 5, 7]))
+
+# Test 5
+# Correct result => -1
+print(find_element_smaller_left_bigger_right([11, 9, 12]))
+
+# Test 6
+# Correct result => 234
+print(find_element_smaller_left_bigger_right([177, 234, 236, 276, 519, 606, 697, 842, 911, 965, 1086, 1135, 1197, 1273, 1392, 1395, 1531, 1542, 1571, 1682, 2007, 2177, 2382, 2410, 2432, 2447, 2598, 2646, 2672, 2826, 2890, 2899, 2916, 2955, 3278, 3380, 3623, 3647, 3690, 4186, 4300, 4395, 4468, 4609, 4679, 4712, 4725, 4790, 4851, 4912, 4933, 4942, 5156, 5186, 5188, 5244, 5346, 5538, 5583, 5742, 5805, 5830, 6010, 6140, 6173, 6357, 6412, 6414, 6468, 6582, 6765, 7056, 7061, 7089, 7250, 7275, 7378, 7381, 7396, 7410, 7419, 7511, 7625, 7639, 7655, 7776, 7793, 8089, 8245, 8622, 8758, 8807, 8969, 9022, 9149, 9150, 9240, 9273, 9573, 9938]))
diff --git a/Arrays/find_el_where_k_greater_or_equal.py b/Arrays/find_el_where_k_greater_or_equal.py
@@ -7,12 +7,16 @@
 
 Input: [3,8,5,1,10,3,20,24], 2
 Output: 11
-Output explanation: Only 20 and 24 are greater or smaller from 11 (11 is the smallest solution, also 12, 13...20 are solutions).
+Output explanation: Only 20 and 24 are equal or smaller from 11 (11 is the smallest solution, also 12, 13...20 are solutions).
 
 =========================================
 Sort the array and check the Kth element from the end.
     Time Complexity:    O(NLogN)
     Space Complexity:   O(1)
+QuickSelect can be used (find the K+1th number + 1). https://en.wikipedia.org/wiki/Quickselect
+See kth_smallest.py, very similar solution.
+    Time Complexity:    O(N)
+    Space Complexity:   O(1)
 '''
 
 
@@ -46,4 +50,4 @@ def get_minimum_X(arr, k):
 
 # Test 1
 # Correct result => 11
-print(get_minimum_X([3, 8, 5, 1, 10, 3, 20, 24], 2))
+print(get_minimum_X([3, 8, 5, 1, 10, 3, 20, 24], 2))
diff --git a/Arrays/k_closest_points.py b/Arrays/k_closest_points.py
@@ -13,6 +13,9 @@
    Time Complexity:     O(N)    , O(N + N/2 + N/4 + N/8 + ... + 1 = 2*N = N)
    Space Complexity:    O(K)    , length of the output array
 Completely the same algorithm as the previous one, but without recursion. This solution is cleaner.
+This algorithm is called: QucikSelect - The quicksort pivoting logic but for searching kth smallest (not sorting the whole array) - O(n) complexity (n + n/2 + n/4 + ... + 1 = 2n)
+https://en.wikipedia.org/wiki/Quickselect
+Same solution as kth_smallest.py.
     Time Complexity:    O(N)
     Space Complexity:   O(K)
 '''
@@ -111,4 +114,4 @@ def find_k_closes(arr, pt, k):
 # Test 2
 # Correct result => [(1, 2), (2, 1)]
 print(find_k_closes_recursive([(0, 1), (2, 1), (3, 3), (1, 2)], (2, 2), 2))
-print(find_k_closes([(0, 1), (2, 1), (3, 3), (1, 2)], (2, 2), 2))
+print(find_k_closes([(0, 1), (2, 1), (3, 3), (1, 2)], (2, 2), 2))
diff --git a/Arrays/kth_smallest.py b/Arrays/kth_smallest.py
@@ -18,6 +18,8 @@
    Time Complexity:     O(N)    , O(N + N/2 + N/4 + N/8 + ... + 1 = 2*N = N)
    Space Complexity:    O(LogN) , because of the recursion stack
 Completely the same algorithm as the previous one, but without recursion. This solution is cleaner.
+This algorithm is called: QucikSelect - The quicksort pivoting logic but for searching kth smallest (not sorting the whole array) - O(n) complexity (n + n/2 + n/4 + ... + 1 = 2n)
+https://en.wikipedia.org/wiki/Quickselect
     Time Complexity:    O(N)
     Space Complexity:   O(1)
 '''
@@ -119,4 +121,4 @@ def find_kth_smallest(arr, k):
 # Correct result => 1 2 3 4 5
 arr = [5, 4, 3, 2, 1]
 print([find_kth_smallest_recursive(arr, i) for i in range(1, len(arr) + 1)])
-print([find_kth_smallest(arr, i) for i in range(1, len(arr) + 1)])
+print([find_kth_smallest(arr, i) for i in range(1, len(arr) + 1)])
diff --git a/Arrays/top_k_frequent_elements.py b/Arrays/top_k_frequent_elements.py
@@ -16,7 +16,9 @@
     Time Complexity:    O(U LogK)   , U in this case is the number of unique elements (but all elements from the array could be unique, so because of that U can be equal to N)
     Space Complexity:   O(N)
 Using pivoting, this solution is based on the quick sort algorithm (divide and conquer).
-Same pivoting solution as the nth_smallest.py.
+This algorithm is called: QucikSelect - The quicksort pivoting logic but for searching kth smallest (not sorting the whole array) - O(n) complexity (n + n/2 + n/4 + ... + 1 = 2n)
+https://en.wikipedia.org/wiki/Quickselect
+Same solution as kth_smallest.py.
     Time Complexity:    O(U)
     Space Complexity:   O(N)
 '''
@@ -161,4 +163,4 @@ def swap(arr, i, j):
 # Test 2
 # Correct result => [1]
 print(top_k_frequent_1([1], 1))
-print(top_k_frequent_2([1], 1))
+print(top_k_frequent_2([1], 1))
diff --git a/README.md b/README.md
@@ -174,7 +174,6 @@ If the problems from [LeetCode](https://leetcode.com/) are not enough and you ne
 - [Topcoder](http://topcoder.com/)
 - [Project Euler](https://projecteuler.net/)
 - [SPOJ](http://www.spoj.com/)
-- [A2OJ](https://a2oj.com/)
 - [PEG](https://wcipeg.com/)
 - [Online Judge](https://onlinejudge.org/)
 - [E-Olymp](https://www.e-olymp.com/en/)
@@ -183,7 +182,6 @@ If the problems from [LeetCode](https://leetcode.com/) are not enough and you ne
 - [USA CO](http://www.usaco.org/)
 - [Rosetta Code](http://rosettacode.org/)
 - [AtCoder](https://atcoder.jp/)
-- [Russian Code Cup](https://www.russiancodecup.ru/en/)
 - [LintCode](http://www.lintcode.com/en/)
 - [Kattis](https://www.kattis.com/developers)
 - [CodeAbbey](http://codeabbey.com/)
@@ -196,11 +194,9 @@ If the problems from [LeetCode](https://leetcode.com/) are not enough and you ne
 - [Codewars](http://www.codewars.com/)
 - [Wolfram Challenges](https://challenges.wolfram.com/)
 - [Google's Coding Competitions](https://codingcompetitions.withgoogle.com/)
-- [Google Foobar](https://foobar.withgoogle.com/)
 - [Cyber-dojo](https://cyber-dojo.org/)
 - [CodingBat](http://codingbat.com/)
 - [CodeKata](http://codekata.com/)
-- [BinarySearch](https://binarysearch.io/)
 - [Daily Coding Problem](https://www.dailycodingproblem.com/)
 - [Daily Interview Pro](http://dailyinterviewpro.com/)
 - [AlgoDaily](https://algodaily.com/)
@@ -213,7 +209,6 @@ If the problems from [LeetCode](https://leetcode.com/) are not enough and you ne
 - [Brilliant](http://brilliant.org/)
 - [Codingame](https://www.codingame.com/)
 - [CheckiO](http://www.checkio.org/)
-- [FightCode](http://fightcodegame.com/)
 - [Kaggle](http://kaggle.com/)
 - [Rosalind](http://rosalind.info/problems/locations/)
 - [workat.tech](https://workat.tech/problem-solving/practice/)
@@ -230,13 +225,12 @@ If the problems from [LeetCode](https://leetcode.com/) are not enough and you ne
     - [Algorithm Visualizer](https://algorithm-visualizer.org/) - Interactive online platform that visualizes algorithms from code. This platform is an open-source project, [here](https://github.com/algorithm-visualizer/algorithm-visualizer) you can find the source code.
 5. Courses and tutorials (but not from universities like the [Courses](#Courses) section):
     - [Google - Intro to Data Structures and Algorithms](https://www.udacity.com/course/data-structures-and-algorithms-in-python--ud513) - Free course on Udacity offered by Google.
-    - [Microsoft - Algorithms and Data Structures](https://www.edx.org/course/algorithms-and-data-structures) - Free course on edX offered by Microsoft.
     - [HackerEarth - Tutorials and Practice](https://www.hackerearth.com/practice/) - Practice problems and learn about many algorithms and data structures needed for competitive programming.
     - [KhanAcademy - Algorithms](https://www.khanacademy.org/computing/computer-science/algorithms) - Good explanations for some basic algorithms.
     - [Tutorialspoint - Data Structures and Algorithms](https://www.tutorialspoint.com/data_structures_algorithms/index.htm) - Another platform with good explanations, also Tutorialspoint has free tutorials for almost everything related to CS!
     - [Programiz - Data Structures and Algorithms](https://www.programiz.com/dsa) - One more platform which explains the data structures and algorithms in a simple and interesting way.
     - [Hackr.io - Data Structures and Algorithms Tutorials and Courses](https://hackr.io/tutorials/learn-data-structures-algorithms) - Big collection of tutorials and courses.
-    - [Scaler - Data Structures Tutorial](https://www.scaler.com/topics/data-structures/) - Learn in-depth about the need & applications of data structures.
+    - [Scaler - Data Structures Tutorial](https://www.scaler.com/topics/data-structures/) - Interesting and interactive explanations of some basic data structures.
 6. YouTube playlists with tutorials:
     - [Data Structures by mycodeschool](https://www.youtube.com/playlist?list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P)
     - [Data Structures by HackerRank](https://www.youtube.com/playlist?list=PLI1t_8YX-Apv-UiRlnZwqqrRT8D1RhriX)
