Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

class Solution {
public:
    int numSquares(int n) {
        // recursion done with one for loop.
        if (n < 4) {
            return n;
        }
        // Dynamic
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3;
       
        for (int i = 4; i <= n; i++) {
            if (dp[i] == INT_MAX) {
                for (int j = 1; j <= sqrt(i); j++) {
                    dp[i] = min(dp[i], dp[i - j*j] + 1);
                }
            }
        }
        return dp[n];
    }
};

==================== Efficient one ==========

int numSquares(int n) { int dp[n+1]; dp[0] = 0; dp[1] = 1; for(int i=2; i<=n; i++){ dp[i]=i; for(int j=1; j*j<=i; j++){ int x = dp[i-j*j]+1; dp[i]= min(dp[i],x); } } return dp[n]; }

Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

class Solution {

public:

    bool searchMatrix(vector<vector<int>>& matrix, int target) {

        int rows = matrix.size();

        if (rows == 0) {

            return false;

        }

        int cols = matrix[0].size();

        int rows_st = 0;

        int cols_end = cols;

        while (rows_st < rows && cols_end > 0) {

            int row = rows_st, col = cols_end - 1;

            if (matrix[row][col] == target) {

                return true;

            } else if (matrix[row][col] > target) {

                cols_end--;

            } else {

                rows_st++;

            }

        }

        return false;

    }

};

Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

=========================================================

class Solution {

public:

    struct comp {

        bool operator()(pair<int, int> first, pair<int,int> second) {

            return first.second < second.second;

        }

    };

    

    vector<int> topKFrequent(vector<int>& nums, int k) {

        map<int, int> mp;

        priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;

        

        for (int num : nums) {

            mp[num]++;

        }

        

        for (auto entry : mp) {

            pq.push(make_pair(entry.first, entry.second));

        }

        

        // since k is always valid.

        vector<int> ans;

        for (int i = 0 ; i < k; i++) {

            int elem = pq.top().first;

            ans.push_back(elem);

            pq.pop();

        }

        

        return ans;

    }

};

======================== Order n space n ==========

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        vector<vector<int>> bucket(nums.size() + 1);
        vector<int> res;
        for (auto a : nums) ++m[a];
        for (auto it : m) {
            bucket[it.second].push_back(it.first);
        }
        for (int i = nums.size(); i >= 0; --i) {
            for (int j = 0; j < bucket[i].size(); ++j) {
                res.push_back(bucket[i][j]);
                if (res.size() == k) return res;
            }
        }
        return res;
    }
};