BFS: Shortest Reach in a Graph

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static class Graph {

        ArrayList<ArrayList<Integer>> adj;
        int size;

        public Graph(int size) {
            adj = new ArrayList<ArrayList<Integer>>(size);
            for (int i = 0; i < size; i++)
                adj.add(new ArrayList<Integer>());
            this.size = size;
        }

        public void addEdge(int first, int second) {
            adj.get(first).add(second);
            adj.get(second).add(first);
        }

        public int[] shortestReach(int startId) { // 0 indexed
            int[] dist = new int[this.size];
            Arrays.fill(dist, -1);
            Queue<Integer> q = new LinkedList<Integer>();
            boolean v[] = new boolean[this.size];
            q.add(startId);
            v[startId] = true;
            dist[startId] = 0;

            while (!q.isEmpty()) {
                int current = q.poll();

                for (Integer distNode : adj.get(current)) {
                    if (!v[distNode]) {
                        v[distNode] = true;
                        dist[distNode] = dist[current] + 6;
                        q.add(distNode);
                    }
                }
            }

            return dist;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int queries = scanner.nextInt();

        for (int t = 0; t < queries; t++) {

            // Create a graph of size n where each edge weight is 6:
            Graph graph = new Graph(scanner.nextInt());
            int m = scanner.nextInt();

            // read and set edges
            for (int i = 0; i < m; i++) {
                int u = scanner.nextInt() - 1;
                int v = scanner.nextInt() - 1;

                // add each edge to the graph
                graph.addEdge(u, v);
            }

            // Find shortest reach from node s
            int startId = scanner.nextInt() - 1;
            int[] distances = graph.shortestReach(startId);

            for (int i = 0; i < distances.length; i++) {
                if (i != startId) {
                    System.out.print(distances[i]);
                    System.out.print(" ");
                }
            }
            System.out.println();
        }

        scanner.close();
    }
}

1295. Find Numbers with Even Number of Digits

class Solution {
    public int countDigits(int num){
        int count = 1;
        while(num /10 !=0){
            num = num /10;
            count++;
        }
        return count;
    }
    public int findNumbers(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++){
            if(countDigits(nums[i]) % 2 == 0) count++;
        }
        return count;
    }
}

1200. Minimum Absolute Difference

Brute Force: Time Limit Exceed

class Solution {
    public List<List> minimumAbsDifference(int[] arr) {
        List<List> out = new ArrayList();
        int minAbs = Integer.MAX_VALUE;
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++){
            for (int j= i+1; j < arr.length; j++){
                minAbs = Math.min(minAbs, Math.abs(arr[i] - arr[j]));
            }
        }
        
         for (int i = 0; i < arr.length; i++){
            for (int j= i+1; j < arr.length; j++){
                if(Math.abs(arr[i] - arr[j]) == minAbs) {
                    ArrayList pair = new ArrayList();
                    pair.add(arr[i]);
                    pair.add(arr[j]);
                    out.add(pair);
                }
            }
        }
     return out;   
    }
}

Easy Optimization:

class Solution {
    public List<List> minimumAbsDifference(int[] arr) {
        List<List> out = new ArrayList();
        int minAbs = Integer.MAX_VALUE;
        Arrays.sort(arr);
        //LinkedHashMap to preserve the insertion order
        LinkedHashMap index = new LinkedHashMap();
        for (int i = 0; i  Math.abs(arr[i+1] - arr[i])){
                minAbs = Math.abs(arr[i+1] - arr[i]);
                index = new LinkedHashMap();
                index.put(i,i+1);
            }
        }
        
        for (Integer a : index.keySet()){
            ArrayList in = new ArrayList();
            in.add(arr[a]);
            in.add(arr[index.get(a)]);
            out.add(in);
        }
     return out;   
    }
}

1337. The K Weakest Rows in a Matrix

class Solution {
    private class Row{
	int rowNum;
	int soliders;
	public Row(int rowNum, int soliders) {
		this.rowNum = rowNum;
		this.soliders = soliders;
 	}
	public int getRowNum() {
		return rowNum;
	}
	public void setRowNum(int rowNum) {
		this.rowNum = rowNum;
	}
	public int getSoliders() {
		return soliders;
	}
	public void setSoliders(int soliders) {
		this.soliders = soliders;
	}
	
}
   public int[] kWeakestRows(int[][] mat, int k) {
    	int rowCount =0;
    	ArrayList rows = new ArrayList();
    	int i = 0;
        for(i =0; i < mat.length; i++) {
        	rowCount =0;
        	for (int j = 0; j < mat[i].length; j++) {
        		if(mat[i][j] == 1) rowCount++;
        	}
        	rows.add(new Row(i,rowCount));
        }
             Collections.sort(rows, new Comparator(){
			@Override
			public int compare(Row o1, Row o2) {
				if (o1.getSoliders() == o2.getSoliders()) 
					{
					return  ((Integer)o1.getRowNum()).compareTo((Integer)o2.getRowNum());
					}
				return ((Integer)o1.getSoliders()).compareTo((Integer)o2.getSoliders());
			}});
        int[] out = new int[k];
        for (int j = 0; j < out.length; j++) {
        	out[j] = rows.get(j).getRowNum();
        }
        return out;
    }
}

1356. Sort Integers by The Number of 1 Bits

class Solution {
public int[] sortByBits(int[] arr) {
		Integer[] arrObject = new Integer[arr.length];
		for (int i = 0; i < arr.length; i++) {
			arrObject[i] = arr[i];
		}
		Arrays.sort(arrObject, new Comparator() {

			@Override
			public int compare(Integer o1, Integer o2) {
				if (countOnes(o1) == countOnes(o2))
					return o1.compareTo(o2);
				else if (countOnes(o1) > countOnes(o2))
					return 1;
				else
					return -1;

			}
		});

		for (int i = 0; i < arr.length; i++) {
			arr[i] = arrObject[i];
		}
		return arr;
	}

	public static int countOnes(int n) {
		int count = 0;
		while (n != 0) {
			n = n & (n - 1);
			count++;
		}
		return count;
	}
}

1207. Unique Number of Occurrences

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        HashMap h = new HashMap();
        for(int i = 0; i < arr.length; i++) {
        	h.put(arr[i], h.getOrDefault(arr[i],0)+1);
        }
        if(h.size() == 0) return true;
        HashSet repeats = new HashSet();
       
        for (Integer a: h.keySet()) {
        	if(repeats.contains(h.get(a))) return false;
        	else repeats.add(h.get(a));
        }
        return true;
    }
}

1022. Sum of Root To Leaf Binary Numbers

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int sum = 0;
    public void construct(TreeNode root,String prev){
        if (root == null) return;
        if( root.left == null && root.right == null){
            sum+=Integer.parseInt(prev+root.val,2);
            return;
        }
       construct(root.left,prev+""+root.val);
       construct(root.right,prev+""+root.val);    
    }
    public int sumRootToLeaf(TreeNode root) {
        if (root == null) return 0;
        if(root.left == null && root.right == null) return root.val;
         construct(root.left,root.val+"");
         construct(root.right,root.val+"");
        return sum;
    }
}

1047. Remove All Adjacent Duplicates In String

class Solution {
    public String removeDuplicates(String S) {
        if(S == null || S.isEmpty()) return "";
        if(S.length() ==1) return S;
        for (int i = 0; i < S.length() - 1; i++){
            if(S.charAt(i) == S.charAt(i+1))
                return removeDuplicates(S.substring(0,i)+S.substring(i+2));
        }
        return S;
    }
}

107. Binary Tree Level Order Traversal II

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List> levelOrderBottom(TreeNode root) {
        if (root == null) return new LinkedList();
        List<List> out = new ArrayList();
Queue   q = new LinkedList(); 
        q.offer(root);
        while(!q.isEmpty()){
            ArrayList current = new ArrayList();
            int size = q.size();//we must put it in variable is the size changes each loop
            for(int i =0; i < size; i++){
            TreeNode c = q.poll();
            if(c != null){
                current.add(c.val);
            if(c.left != null)
                q.offer(c.left);
            if(c.right != null)
                q.offer(c.right);
            }
            
        }
            out.add(current);
        }
         Collections.reverse(out);
        return out;
    }
    
}