algorithms

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

commit 15d7caf7886b9e3707979569ba89d8120355c9b9
parent f935525f4143abb7b839c9391f071e5dba92495e
Author: Andrew Laack <andrew@laack.co>
Date:   Sat, 31 Oct 2026 16:20:33 -0500

Various leetcode problems

Diffstat:
Aleetcode/house-robber/house-robber.cpp | 32++++++++++++++++++++++++++++++++
Aleetcode/maximum-subarray/maximum-subarray-v3.cpp | 20++++++++++++++++++++
Aleetcode/minimum-operations-to-sort-a-permutation/minimum-operations-to-sort-a-permutation.cpp | 68++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aleetcode/minimum-size-subarray-sum/minimum-size-subarray-sum.cpp | 46++++++++++++++++++++++++++++++++++++++++++++++
Aleetcode/shortest-path-with-at-most-k-consecutive-identical-characters/shortest-path-with-at-most-k-consecutive-identical-characters.cpp | 68++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 234 insertions(+), 0 deletions(-)

diff --git a/leetcode/house-robber/house-robber.cpp b/leetcode/house-robber/house-robber.cpp @@ -0,0 +1,32 @@ +class Solution { +public: + + int getBest(int idx, vector<int>& nums, vector<int>& best) { + + if(idx >= nums.size()) { + return 0; + } + + if(best[idx] != -1) { + return best[idx]; + } + + int nextBest = getBest(idx+1, nums,best); + int p1Best = getBest(idx+2, nums,best); + int cur = std::max(nextBest, p1Best + nums[idx]); + best[idx] = cur; + + return cur; + } + int rob(vector<int>& nums) { + // ideas: + // greedy? x + // dp? + // recurse + // from the end: + // best is to take current + // compare current best with next best and set it as such + vector<int> best = vector<int>(nums.size(), -1); + return getBest(0,nums, best); + } +}; diff --git a/leetcode/maximum-subarray/maximum-subarray-v3.cpp b/leetcode/maximum-subarray/maximum-subarray-v3.cpp @@ -0,0 +1,20 @@ +class Solution { +public: + int maxSubArray(vector<int>& nums) { + int sm = 0; + int best = -100000; + + for(int i = 0; i < nums.size(); ++i) { + sm += nums[i]; + if(sm > best) { + best = sm; + } + if(sm < 0) { + sm = 0; + } + + } + + return best; + } +}; diff --git a/leetcode/minimum-operations-to-sort-a-permutation/minimum-operations-to-sort-a-permutation.cpp b/leetcode/minimum-operations-to-sort-a-permutation/minimum-operations-to-sort-a-permutation.cpp @@ -0,0 +1,68 @@ +class Solution { +public: + int minOperations(vector<int>& nums) { + // permutation of n-1 + // this means 0 -> n is the sorted + + // ops: + // reverse array + // rotate left by one + + // return min op count or -1 + + // idea: + // we just rotate left by one until it matches the n-1 -> 0 array + // then return ops + 1 + // are there cases where we invert first? + // inversion makes sense to go to right + // since these are all in one, + // we might want to try both ways? + + // check if there's a monotonically increasing walk with at most one exclusion + + int idxZero = -1; + int maxIdx = -1; + + for(int i = 0; i < nums.size(); ++i) { + if(nums[i] == 0) { + idxZero = i; + } + if(nums[i] == nums.size() - 1) { + maxIdx = i; + } + } + + bool monoLeft = true; + bool monoRight = true; + + for(int i = idxZero+1; i < nums.size() + idxZero; ++i) { + if(nums[i % nums.size()] < nums[(i+nums.size() - 1) % nums.size()]) { + monoRight = false; + break; + } + } + + if(!monoRight) { + for(int i = maxIdx + 1; i < nums.size() + maxIdx ; ++i) { + if(nums[i % nums.size()] > nums[(i+nums.size() - 1) % nums.size()]) { + cout << nums[i % nums.size()] << endl; + cout << nums[(i+nums.size() - 1) % nums.size()] << endl; + return -1; + } + } + } + + int n = nums.size(); + + if(monoRight) { + int shiftLeftCost = idxZero; + int shiftRightCost = (n - idxZero) + 2; + return min(shiftLeftCost, shiftRightCost); + } else { + int shiftLeftCost = maxIdx + 1; + int shiftRightCost = 1 + (n - maxIdx) % n; + return min(shiftLeftCost, shiftRightCost); + } + return 0; + } +}; diff --git a/leetcode/minimum-size-subarray-sum/minimum-size-subarray-sum.cpp b/leetcode/minimum-size-subarray-sum/minimum-size-subarray-sum.cpp @@ -0,0 +1,46 @@ +class Solution { +public: + int minSubArrayLen(int target, vector<int>& nums) { + // find the shortest contiguous subarray (redundant) whose sum is at least target + // first thought: + // can we use prefix sums? + // idea: + // compute inclusive prefix sums for each element + // O(n^2) tc bc we check each pairing + // hashmaps are out + // sliding window + // start from left side + // if current sum < target move right ptr + // if current sum >= target move left ptr + + int leftPtr = 0; + int rightPtr = 0; + int sum = nums[0]; + int shortest = nums.size()+2; + while(rightPtr < nums.size()) { + if(sum >= target) { + if((rightPtr - leftPtr) + 1 < shortest) { + shortest = (rightPtr - leftPtr) + 1; + } + if(leftPtr < rightPtr) { + sum -= nums[leftPtr]; + leftPtr += 1; + } else { + rightPtr += 1; + if(rightPtr < nums.size()) { + sum += nums[rightPtr]; + } + } + } else { + rightPtr += 1; + if(rightPtr < nums.size()) { + sum += nums[rightPtr]; + } + } + } + if(shortest == nums.size() + 2) { + return 0; + } + return shortest; + } +}; diff --git a/leetcode/shortest-path-with-at-most-k-consecutive-identical-characters/shortest-path-with-at-most-k-consecutive-identical-characters.cpp b/leetcode/shortest-path-with-at-most-k-consecutive-identical-characters/shortest-path-with-at-most-k-consecutive-identical-characters.cpp @@ -0,0 +1,68 @@ +class Solution { +public: + + // priors is only for cycle detection, not necessary to memoize. + int solve(int n, unordered_map<int,vector<pair<int,int>>> &edges, string labels, int k) { + + // djikstra's algo + // push to heap with edges as found + // edge encoding: + // (cost, destination, consecutive) + + priority_queue<vector<int>> pq; + pq.push({0,0,0}); + + unordered_map<string,int> best {}; + + // not super fast bc copies + string stuff, but it works. + while(!pq.empty()) { + vector<int> current = pq.top(); + vector<pair<int,int>>& el = edges[current[1]]; + int cCost = current[0]; + string cs = to_string(current[1]) + " " + to_string(current[2]); + if(best.contains(cs)) { + if(best[cs] <= -cCost) { + pq.pop(); + continue; + } else { + best[cs] = -cCost; + } + } else { + best[cs] = -cCost; + } + + if(current[1] == n-1) { + return -current[0]; + } + + for(int i = 0; i < el.size(); ++i) { + if(labels[current[1]] == labels[el[i].first]) { + int cons = current[2]; + cons += 1; + if(cons >= k) { + continue; + } + pq.push({-el[i].second + cCost, el[i].first, cons}); + } else { + pq.push({-el[i].second + cCost, el[i].first, 0}); + } + } + pq.pop(); + } + return -1; + + + } + int shortestPath(int n, vector<vector<int>>& edges, string labels, int k) { + + unordered_map<int, vector<pair<int,int>>> edgeList {}; + for(int i = 0; i < edges.size(); ++i) { + auto& current = edges[i]; + edgeList[current[0]].push_back({current[1], current[2]}); + } + + int res = solve(n,edgeList,labels,k); + + return res; + } +};