algorithms

commit a8bb40057a4fb291131de0c41a1cd13b73486bd4
parent 9b6e2d120e2ac998acad4c90f755ebd8a6e6fb46
Author: Andrew Laack <andrew@laack.co>
Date:   Sat, 12 Sep 2026 10:26:13 -0500

Quickselect

Diffstat:
A
lc/kth-largest-element-in-an-array/kth-largest-element-in-an-arrayV1.cpp
 | 
49
+++++++++++++++++++++++++++++++++++++++++++++++++
A
lc/kth-largest-element-in-an-array/kth-largest-element-in-an-arrayV2.cpp
 | 
55
+++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 104 insertions(+), 0 deletions(-)
diff --git a/lc/kth-largest-element-in-an-array/kth-largest-element-in-an-arrayV1.cpp b/lc/kth-largest-element-in-an-array/kth-largest-element-in-an-arrayV1.cpp
@@ -0,0 +1,49 @@
+class Solution {
+public:
+    void swap(vector<int>& nums, int p1, int p2) {
+        int temp = nums[p1];
+        nums[p1] = nums[p2];
+        nums[p2] = temp;
+        return;
+    }
+    int quickSelect(vector<int>& nums, int k, int left, int right) { 
+        int rightPos = right;
+        int rndPos = right;
+        if(right - left > 0) {
+            rndPos = rand() % (right - left) + left;
+        }
+        int leftPos = left;
+        int pivotValue = nums[rndPos];
+        swap(nums,right,rndPos);
+        rightPos -= 1;
+        int i = left;
+
+        while (i <= rightPos) {
+            if (nums[i] >= pivotValue) {
+                swap(nums, i, rightPos);
+                rightPos--;
+            } else {
+                swap(nums, i, leftPos);
+                leftPos++;
+                i++;
+            }
+        }        
+        int pivotIndex = rightPos+1;
+        swap(nums,pivotIndex,right);
+
+        if(pivotIndex == k) {
+            return nums[pivotIndex];
+        }
+        if(pivotIndex < k) {
+            return quickSelect(nums,k,pivotIndex+1,right);
+        }
+        if(pivotIndex > k) {
+            return quickSelect(nums,k,left,pivotIndex-1);
+        }
+        return -1;
+
+    }
+    int findKthLargest(vector<int>& nums, int k) {
+        return quickSelect(nums,nums.size() - k,0,nums.size()-1);
+    }
+};
diff --git a/lc/kth-largest-element-in-an-array/kth-largest-element-in-an-arrayV2.cpp b/lc/kth-largest-element-in-an-array/kth-largest-element-in-an-arrayV2.cpp
@@ -0,0 +1,55 @@
+class Solution {
+public:
+    void swap(vector<int>& nums, int p1, int p2) {
+        int temp = nums[p1];
+        nums[p1] = nums[p2];
+        nums[p2] = temp;
+        return;
+    }
+    int quickSelect(vector<int>& nums, int k, int left, int right) { 
+        int rightPos = right;
+        int rndPos = right;
+        if(right - left > 0) {
+            rndPos = rand() % (right - left) + left;
+        }
+        int leftPos = left;
+        int pivotValue = nums[rndPos];
+        swap(nums,right,rndPos);
+        rightPos -= 1;
+        int i = left;
+
+        int matchCount = 0;
+
+        while (i <= rightPos) {
+            if (nums[i] >= pivotValue) {
+                if (pivotValue == nums[i]) {
+                    matchCount += 1;
+                }
+                swap(nums, i, rightPos);
+                rightPos--;
+            } else {
+                swap(nums, i, leftPos);
+                leftPos++;
+                i++;
+            }
+        }
+
+        int pivotIndex = rightPos+1;
+        swap(nums,pivotIndex,right);
+
+        if(pivotIndex + matchCount >= k && pivotIndex <= k) {
+            return nums[pivotIndex];
+        }
+        if(pivotIndex < k) {
+            return quickSelect(nums,k,pivotIndex+1,right);
+        }
+        if(pivotIndex > k) {
+            return quickSelect(nums,k,left,pivotIndex-1);
+        }
+        return -1;
+
+    }
+    int findKthLargest(vector<int>& nums, int k) {
+        return quickSelect(nums,nums.size() - k,0,nums.size()-1);
+    }
+};