27. Remove Element

Problem Link

27. Remove Element

Problem Description

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Solution

Iterate through the array, swapping non-matching elements to the front.

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size(), pos = 0;
        for (int i = 0; i < size; ++i) {
            if (nums[i] == val)
                continue;
            swap(nums[pos], nums[i]);
            pos++;
        }
        return pos;
    }
};

179. Largest Number

Problem Link

179. Largest Number

Problem Description

Given a list of non-negative inteegrs nums, arrange them such that they form largest number and return it.

Since the result may be very large, return a string instead of an integer.

Soluiton

Use a greedy approach: compare two numbers based on which arrangement produces a larger combined number.

Note: The helper function f() may overflow int.

class Solution {
public:
    long long f(int x) {
        long long base = 10;
        while (x >= base) base *= 10;
        return base;
    }

    string largestNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [&](int& a, int& b) {
            long long base_a = f(a), base_b = f(b);
            return 1LL * a * base_b + b > 1LL * b * base_a + a;
        });
        if (nums[0] == 0) return "0";
        string result = "";
        for (int num : nums)
            result += to_string(num);
        return result;
    }
};

75. Sort Colors

Problem Link

75. Sort Colors

Problem Description

Given an array with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Solution

Traverse once, move 0s to the left and 2s to the right, handling boundaries carefully.

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int len = nums.size(), left = 0, right = len - 1;
        for (int i = left; i <= right; ++i) {
            if (nums[i] == 0)
                swap(nums[left++], nums[i--]);
            else if (nums[i] == 2)
                swap(nums[right--], nums[i--]);
            if (i < left - 1) i = left - 1;
        }
    }
};

215. Kth Largest Element in an Array

Problem Link

215. Kth Largest Element in an Array

Problem Description

Find the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Solution

Quick Sort

The partition function in quick sort is unstable, so it's not suitable for all test cases. This is mainly for reviewing quick sort implementation.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size(), l = 0, r = n - 1, current = -1, target = n - k;
        while (current != target) {
            if (current < target)
                current = partition(nums, current + 1, r);
            else
                current = partition(nums, l, current - 1);
        }
        return nums[current];
    }

    int partition(vector<int>& a, int begin, int end) {
        int left = begin, right = end;
        while (left < right) {
            while (left < end && a[left] <= a[begin])
                left++;
            while (begin < right && a[right] >= a[begin])
                right--;
            if (left < right)
                swap(a[left], a[right]);
        }
        swap(a[begin], a[right]);
        return right;
    }
};

Binary Search

Handle positive and negative numbers correctly with boundary checks.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int low = -10005, high = 10005;
        while (low < high) {
            int mid = (low + high) / 2 + 1;
            if (low + high < 0) mid--;
            int count = 0;
            for (int x : nums)
                if (x >= mid) count++;
            if (count < k)
                high = mid - 1;
            else
                low = mid;
        }
        return low;
    }
};

Max Heap

Implement a max heap manually.

class Solution {
public:
    void heapify(vector<int>& arr, int index) {
        if (index < 0) return;
        int size = arr.size();
        if (index >= size) return;
        int left = 2 * index + 1, right = 2 * index + 2;
        if (left >= size) return;
        if (right == size) {
            if (arr[index] < arr[left]) swap(arr[index], arr[left]);
            return;
        }
        if (arr[index] >= arr[left] && arr[index] >= arr[right]) return;
        int nextIndex = (arr[left] > arr[index] && arr[left] >= arr[right]) ? left : right;
        swap(arr[index], arr[nextIndex]);
        heapify(arr, nextIndex);
    }

    void build(vector<int>& arr) {
        int size = arr.size();
        for (int i = size / 2 - 1; i >= 0; --i) heapify(arr, i);
    }

    void extractMax(vector<int>& arr) {
        arr[0] = -100000;
        heapify(arr, 0);
    }

    int findKthLargest(vector<int>& nums, int k) {
        build(nums);
        for (int i = 0; i < k - 1; ++i) extractMax(nums);
        return nums[0];
    }
};