# 1337. The K Weakest Rows in a Matrix

## Tóm tắt đề
Cho $m\times n$ matrix được tạo bơi 1 và 0. Số 1 tương ứng với người lình và số 0 tương ứng với dân thường.
Người lính sẽ đừng trước dân thường.
Cho hai hàng $i$ và $j$. Hàng $i$ sẽ yếu hơn hàng $j$ nếu một trong 2 điều kiện sau thỏa mãn:
1. Số người lính ở hàng $i$ ít hơn hàng $j$
2. Số người lính ở hàng $i$ bằng số người lính ở hàng $j$ và $i < j$

Tìm k hàng yếu nhất.

## Giới hạn
$2 \leq n, m \leq 100$
$1 \leq k \leq m$

## Lời giải
Chúng ta cần so sánh người lính với các hàng với nhau, để tìm được só hàng yếu nhất. Dưới đây sẽ là các cách để giải bài toán.

### Linear Search + Sorting
1. Tìm số người lính của mỗi hàng bằng cách loop qua từng hàng
2. Lưu só người lính của từng hàng và index của hàng vào một pair rồi lưu pair đó vào v. Pair sẽ có thứ tự như sau: Phần tử 1 là số người lính, phần tử 2 là index. (Mình làm vậy vì muốn lưu thứ tự của index ban đầu sau khi sort ở bước tiếp theo).
3. Sort vector v. Hàm default sort của C++ sẽ sort ưu tiên index bé hơn. Nếu index đầu tiền bé hơn thì sẽ compare index thứ 2, etc. Nên hàng có người lính sẽ tăng dần trong vector v. Nếu 2 hàng có người lính bằng nhau thì hàng có index bé hơn sẽ ở trên trước.
4. Lấy k hàng cần tìm ra khỏi v và trả kết quả

public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        vector<pair<int,int>> v; 
        for (int i = 0; i < mat.size(); i++) {
            int tmp = 0; 
            for (int j = 0; j < mat[i].size(); j++) {
                tmp += mat[i][j]; 
            }
            v.push_back({tmp, i}); 
        }
        sort(v.begin(), v.end());
        vector<int> ans;  
        for (int i = 0; i < k; i++) {
            ans.push_back(v[i].second);
        }
        return ans;
    }
}; 

Độ phức tạp $O(mn + mlogm) = O(m(n+logm))$
### Binary search and sorting
Chúng ta có thể cải tiến linear search ở cách làm đầu tiền bằng binary search. Bới vì tất cả người lính đừng ở phía trước dân thường.
Khi loop qua mỗi hàng mình chạy function binary search. Nó sẽ return số người lính của mỗi hàng. Điều này đùng vì điều kiện của để bài tất cả người lính đứng trước dân thường.

class Solution {
public:  
    int binarySearch(vector<int> v) {
        int low = 0; 
        int high = v.size();
        int mid;  
        while (low < high) {
            mid = low + (high-low)/2;
            if (v[mid] == 1) {
                low = mid + 1; 
            } else {
                high = mid; 
            }
        }
        return low; 
    }
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        vector<pair<int,int>> v; 
        for (int i = 0; i < mat.size(); i++) {
            v.push_back({binarySearch(mat[i]), i});  
        } 
        sort(v.begin(), v.end());
        vector<int> ans;  
        for (int i = 0; i < k; i++) {
            ans.push_back(v[i].second);
        }
        return ans;
    }
};

Độ phức tạp $O(mlogn + mlogm) = O(mlog(nm)$

### Binary search and priority queue
Chúng ta cỏ thể cái tiển sorting ở cách làm trước bằng việc dùng priority queue. Số lượng phần tử của priority queue sẽ giới hạn ở k.

class Solution {
public:  
    int binarySearch(vector<int> v) {
        int low = 0; 
        int high = v.size();
        int mid;  
        while (low < high) {
            mid = low + (high-low)/2;
            if (v[mid] == 1) {
                low = mid + 1; 
            } else {
                high = mid; 
            }
        }
        return low; 
    }
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        vector<pair<int,int>> v; 
        priority_queue<pair<int, int>> q; 
        vector<int> ans; 
        for (int i = 0; i < mat.size(); i++) {
            q.push({binarySearch(mat[i]), i});
            if (q.size() > k) {
                q.pop(); 
            }  
        } 
        while (!q.empty()) {
            ans.push_back(q.top().second); 
            q.pop(); 
        } 
        reverse(ans.begin(), ans.end());
        return ans; 
    }
};

Độ phức tạp $O(mlogn + mlogk) = O(nlog(nk))$