The K Weakest Rows in a Matrix

A row i is weaker than row j if the number of soldiers in row i is less than the number of soldiers in row j, or they have the same number of soldiers but i is less than j. Soldiers are always stand in the frontier of a row, that is, always ones may appear first and then zeros.

Example:

Input: mat = 
{{1,1,0,0,0},
 {1,1,1,1,0},
 {1,0,0,0,0},
 {1,1,0,0,0},
 {1,1,1,1,1}}, 
k = 3
Output: [2,0,3]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class KWeakestRowsInMatrix {
    public static void main(String[] args) {
        // given input matrix as square matrix
        int matrix[][] = { { 1, 1, 0, 0, 0 }, { 1, 1, 1, 1, 0 },
             { 1, 0, 0, 0, 0 }, { 1, 1, 0, 0, 0 },
                { 1, 1, 1, 1, 1 } };
        int k = 3;
        ArrayList<Integer> kweak = kWeakestRows(matrix, k);
        for (int i = 0; i < k; i++) {
            System.out.print(kweak.get(i) + " ");
        }

    }

    // method to find the kweakest rows in the matrix
    private static ArrayList<Integer> kWeakestRows(int[][] matrix, int k) {
        List<Pair<Integer, Integer>> v = new ArrayList<Pair<Integer, Integer>>();
        int C = matrix[0].length;
        int index = 0;
        for (int i = 0; i < matrix.length; i++) {
            Arrays.sort(matrix[i]);

            // find the last index where 1 occurs
            index = last(matrix[i], 0, C - 1);
            if (index != -1)
                v.add(new Pair(C - index, i));
            else
                v.add(new Pair(0, i));
        }
        // sorting
        Collections.sort(v);
        ArrayList<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < k; i++) {
            res.add(v.get(i).getSecond());
        }
        return res;
    }

    // binary search
    static int last(int[] arr, int low, int high) {
        if (high >= low) {
            int mid = low + (high - low) / 2;
            if ((mid == 0 || arr[mid - 1] == 0) && arr[mid] == 1)
                return mid;
            if (arr[mid] == 0)
                return last(arr, mid + 1, high);
            else
                return last(arr, low, mid - 1);
        }
        return -1;
    }
}

@SuppressWarnings("rawtypes")
class Pair<F extends Comparable<F>, S extends Comparable<S>>
                     implements Comparable<Pair> {
    private F first;
    private S second;

    public Pair(F first, S second) {
        this.first = first;
        this.second = second;
    }

    public F getFirst() {
        return first;
    }

    public S getSecond() {
        return second;
    }

    @SuppressWarnings("unchecked")
    @Override
    public int compareTo(Pair o) {
        return getFirst().compareTo((F) o.first);
    }

    @Override
    public String toString() {
        return "Pair [first=" + first + ", second=" + second + "]";
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

int last(vector<int> &arr,int low,int high)
{
      if(high>=low)
      {
          int mid=low+(high-low)/2;
        if (( mid== 0||arr[mid-1]==0)&& arr[mid]==1)  
            return mid;
          if(arr[mid]==0)
              return last(arr,mid+1,high);
          else
              return last(arr,low,mid-1);
      }
     return -1;
}

//function to find the kweakest rows 
//in the matrix
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
    vector< pair<int,int > > v;
    int C=mat[0].size(),index;
   for(int i=0;i<mat.size();i++)
      {
       sort(mat[i].begin(),mat[i].end());

       //find the last index where 1 occurs
       index=last(mat[i],0,C-1);
        if(index!=-1)
            v.push_back(make_pair(C-index,i));
        else
           v.push_back(make_pair(0,i));
      }
     sort(v.begin(),v.end());
     vector<int> res;
     for(int i=0;i<k;i++)
          res.push_back(v[i].second);
     return res;
}
int main()
{
  vector<vector<int>> mat={{1,1,0,0,0},
                         {1,1,1,1,0},
                         {1,0,0,0,0},
                         {1,1,0,0,0},
                         {1,1,1,1,1}};
  int k=3;
  vector<int> kweak=kWeakestRows(mat,k);
  for(int i=0;i<k;i++)
     cout<<kweak[i]<<" ";
  return 0;
}