algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

commit f4b688c52ca2c96fd27253797d43384ea7c8d7b7
parent 964fa1713075bd11abf2a4a167ab0973d7163ff1
Author: Andrew Laack <andrew@laack.co>
Date:   Fri, 25 Sep 2026 14:25:29 -0500

Added some more leetcode submissions

Diffstat:
Aleetcode/check-if-its-a-straight-line/check-if-its-a-straight-line.cpp | 34++++++++++++++++++++++++++++++++++
Aleetcode/circle-and-rectangle-overlap/circle-and-rectangle-overlap.py | 81+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aleetcode/lexicographical-number/lexicographical-number.py | 30++++++++++++++++++++++++++++++
Aleetcode/min-ops-to-reduce-x-to-zero/min-ops-to-reduce-x-to-zero.cpp | 36++++++++++++++++++++++++++++++++++++
Aleetcode/rectangle-overlap/rectangle-overlap.py | 97+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aleetcode/reverse-bits/reverse-bits-v1.cpp | 12++++++++++++
Aleetcode/reverse-bits/reverse-bits-v2.cpp | 12++++++++++++
Aleetcode/smallest-index-with-digit-sum-equal-to-index/smallest-index-with-digit-sum-equal-to-index.cpp | 20++++++++++++++++++++
8 files changed, 322 insertions(+), 0 deletions(-)

diff --git a/leetcode/check-if-its-a-straight-line/check-if-its-a-straight-line.cpp b/leetcode/check-if-its-a-straight-line/check-if-its-a-straight-line.cpp @@ -0,0 +1,34 @@ +class Solution { +public: + bool checkStraightLine(vector<vector<int>>& coordinates) { + // 2 <= coordinates.length <= 1000 + int dx = coordinates[0][0] - coordinates[1][0]; + int dy = coordinates[0][1] - coordinates[1][1]; + + bool vertical = (dx == 0); + + for(auto& coord : coordinates) { + + int dxCheck = coord[0] - coordinates[0][0]; + int dyCheck = coord[1] - coordinates[0][1]; + + if(vertical && dxCheck != 0) { + return false; + } else if(vertical) { + continue; + } + + if (dxCheck == 0 && dyCheck == 0) { + continue; + } + + if(((double)dyCheck / (double)dxCheck != (double)dy / (double)dx)) { + return false; + } + + } + + return true; + + } +}; diff --git a/leetcode/circle-and-rectangle-overlap/circle-and-rectangle-overlap.py b/leetcode/circle-and-rectangle-overlap/circle-and-rectangle-overlap.py @@ -0,0 +1,81 @@ +class Solution: + def isVertical(self,p1,p2): + return p1[0] == p2[0] + + def distance(self,p1,p2): + return sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) + + # t == target + # s1 == relevant second scalar + # s2 == relevant second scalar + def nearestPos(self,s1,s2,t): + lv = min(s1,s2) + up = max(s2,s1) + if t < up and t > lv: + return t + else: + if t >= up: + return up + else: + return lv + + def dist(self,a): + return a[2] + def nearest(self, corners, center, radius): + + best_by_edge = [] + + for i in range(0,len(corners)): + for j in range(i,len(corners)): + first = corners[i] + second = corners[j] + if self.isVertical(first, second): + ny = self.nearestPos(first[1], second[1], center[1]) + ns = [first[0], ny] + ns.append(self.distance(ns,center)) + best_by_edge.append(ns) + else: + nx = self.nearestPos(first[0], second[0], center[0]) + ns = [nx,first[1]] + ns.append(self.distance(ns,center)) + best_by_edge.append(ns) + + best_by_edge.sort(key=self.dist) + return best_by_edge[0] + + + def containsNearest(self, corners, center, radius): + np = self.nearest(corners,center,radius) + return self.distance(np,center) <= radius + + def centerEnclosed(self, corners,center): + left = corners[0][0] + right = corners[1][0] + bottom = corners[2][1] + top = corners[0][1] + + if top >= center[1] and bottom <= center[1] and left <= center[0] and right >= center[0]: + return True + return False + + + def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool: + # idea: + # if we consider the point in the rectangle, neares to xCenter,yCenter, if it's in the circle we return true + # other case is circle is totally enclosed + + top_left = (x1,y2) + top_right = (x2,y2) + bottom_left = (x1,y1) + bottom_right = (x2,y1) + + corners = (top_left,top_right,bottom_left,bottom_right) + center = (xCenter,yCenter) + + res = self.containsNearest(corners, center, radius) + if res: + return res + + res = self.centerEnclosed(corners,center) + + return res diff --git a/leetcode/lexicographical-number/lexicographical-number.py b/leetcode/lexicographical-number/lexicographical-number.py @@ -0,0 +1,30 @@ +class Solution: + def lexicalOrder(self, n: int) -> list[int]: + # ideas: + # sorting + # too slow + # some sort of stateless traversal + # prior is something, what's next given prior and max? + # how? + # it's the last number with 0 added to the right side + # if this is too large, increment the final digit + # if that's too large, increment the digit to the left and drop rightmost? + prior = 1 + res = [prior] + for _ in range(0,n-1): + if prior * 10 <= n: + res.append(prior*10) + prior *= 10 + continue + if prior + 1 <= n and (prior + 1) // 10 == prior // 10: + res.append(prior+1) + prior += 1 + continue + + prior = prior // 10 + while (prior + 1) // 10 != prior // 10: + prior = prior // 10 + + prior += 1 + res.append(prior) + return res diff --git a/leetcode/min-ops-to-reduce-x-to-zero/min-ops-to-reduce-x-to-zero.cpp b/leetcode/min-ops-to-reduce-x-to-zero/min-ops-to-reduce-x-to-zero.cpp @@ -0,0 +1,36 @@ +class Solution { +public: + int minOperations(vector<int>& nums, int x) { + unordered_map<int,int> prefixSum{}; + + int sum = 0; + for(int i = 0; i < nums.size(); ++i) { + prefixSum[sum] = i; + sum += nums[i]; + } + + prefixSum[sum] = nums.size(); + + int minNum = 1000000; + + if(sum < x) { + return -1; + } + for(auto& val: prefixSum) { + int target = val.first + (sum - x); + if(prefixSum.find(target) != prefixSum.end()) { + minNum = min( + (int)(nums.size() - (abs(prefixSum[target] - prefixSum[val.first]))), + minNum + ); + } + } + + if(minNum == 1000000) { + return -1; + } else { + return minNum; + } + + } +}; diff --git a/leetcode/rectangle-overlap/rectangle-overlap.py b/leetcode/rectangle-overlap/rectangle-overlap.py @@ -0,0 +1,97 @@ +class Solution: + + def intersect(self, e1,e2): + v1 = e1[0] + v2 = e1[1] + + v3 = e2[0] + v4 = e2[1] + + e1_is_vert = False + e2_is_vert = False + + if v1[0] == v2[0]: + e1_is_vert = True + if v3[0] == v4[0]: + e2_is_vert = True + + if e1_is_vert == e2_is_vert: + return False + + if e1_is_vert: + if v3[1] >= max(v1[1],v2[1]) or v3[1] <= min(v1[1],v2[1]): + return False + if min(v3[0], v4[0]) < v1[0] and max(v3[0], v4[0]) > v1[0]: + return True + return False + else: + if v2[1] >= max(v3[1],v4[1]) or v2[1] <= min(v3[1],v4[1]): + return False + if min(v1[0], v2[0]) < v3[0] and max(v1[0], v2[0]) > v3[0]: + return True + return False + + def contains(self,rect1,rect2): + min_x_1 = rect1[0] + max_x_1 = rect1[2] + min_y_1 = rect1[1] + max_y_1 = rect1[3] + + min_x_2 = rect2[0] + max_x_2 = rect2[2] + min_y_2 = rect2[1] + max_y_2 = rect2[3] + + if min_x_1 >= min_x_2 and max_x_1 <= max_x_2: + if min_y_1 >= min_y_2 and max_y_1 <= max_y_2: + return True + return False + + + def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool: + # [x1,y1, x2,y2] + # bottom left, top right + + # if rec1 and rec2 overlap return true + # must fully overlap not just border + + # top left + top_left = (rec2[0], rec2[3]) + # bottom left + bottom_left = (rec2[0], rec2[1]) + # bottom right + bottom_right = (rec2[2], rec2[1]) + # top right + top_right = (rec2[2], rec2[3]) + + rec2_edges = [ + [top_left, top_right], + [top_left, bottom_left], + [bottom_left, bottom_right], + [bottom_right, top_right] + ] + + # top left + top_left = (rec1[0], rec1[3]) + # bottom left + bottom_left = (rec1[0], rec1[1]) + # bottom right + bottom_right = (rec1[2], rec1[1]) + # top right + top_right = (rec1[2], rec1[3]) + + rec1_edges = [ + [top_left, top_right], + [top_left, bottom_left], + [bottom_left, bottom_right], + [bottom_right, top_right] + ] + + for e1 in rec1_edges: + for e2 in rec2_edges: + if self.intersect(e1,e2): + return True + + if self.contains(rec1,rec2) or self.contains(rec2,rec1): + return True + return False diff --git a/leetcode/reverse-bits/reverse-bits-v1.cpp b/leetcode/reverse-bits/reverse-bits-v1.cpp @@ -0,0 +1,12 @@ +class Solution { +public: + int reverseBits(int n) { + int res = 0; + for(int i = 0; i < 32; ++i){ + int rem = n % 2; + n = n >> 1; + res += rem*(pow(2,31-i)); + } + return res; + } +}; diff --git a/leetcode/reverse-bits/reverse-bits-v2.cpp b/leetcode/reverse-bits/reverse-bits-v2.cpp @@ -0,0 +1,12 @@ +class Solution { +public: + int reverseBits(int n) { + int res = 0; + for(int i = 0; i < 32; ++i){ + int rem = n & 0b1; + n = n >> 1; + res += rem*(pow(2,31-i)); + } + return res; + } +}; diff --git a/leetcode/smallest-index-with-digit-sum-equal-to-index/smallest-index-with-digit-sum-equal-to-index.cpp b/leetcode/smallest-index-with-digit-sum-equal-to-index/smallest-index-with-digit-sum-equal-to-index.cpp @@ -0,0 +1,20 @@ +class Solution { +public: + int indexSum(int num) { + int res = 0; + while (num > 0) { + res += num%10; + num = num / 10; + } + return res; + } + int smallestIndex(vector<int>& nums) { + for(int i = 0; i < nums.size(); ++i) { + int num = nums[i]; + if(indexSum(num) == i) { + return i; + } + } + return -1; + } +};