Find the Running Median

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

public class Solution {

    /*
     * Complete the runningMedian function below.
     */
    static double[] runningMedian(int[] a) {
        /*
         * Write your code here.
         */

        
        double[] out = new double[a.length];
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return -Integer.compare(o1, o2);
            }
        });
        double median = 0;
        if(a.length == 1) {
            out[0] = a[0];
            return out;
        }
        for (int i = 0; i < a.length; i++) {
            if( i == 0) {
                out[0] = a[0];
            } else if (i == 1) {
                minHeap.add(Integer.max(a[0], a[1]));
                maxHeap.add(Integer.min(a[0], a[1]));
                out[i] = ((double) a[i - 1] + (double) a[i]) / 2;
                median = out[i];
            } else {
                       
                if(a[i] > median) {
                   minHeap.add(a[i]);
               } else if(a[i]<= median) {
                   maxHeap.add(a[i]);
               }
                
                if(Math.abs(minHeap.size() - maxHeap.size())>1) {
                    if(minHeap.size() > maxHeap.size())
                        maxHeap.add(minHeap.remove());
                    else minHeap.add(maxHeap.remove());
                }
                
                
                if(minHeap.size() == maxHeap.size())
                out[i] = ((double)minHeap.peek() + (double) maxHeap.peek())/2;
                else if (minHeap.size() > maxHeap.size())
                    out[i] = minHeap.peek().doubleValue();
                else if (maxHeap.size() > minHeap.size())
                    out[i] = maxHeap.peek().doubleValue();
                median = out[i];
                
            }
        }
        return out;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int aCount = Integer.parseInt(scanner.nextLine().trim());

        int[] a = new int[aCount];

        for (int aItr = 0; aItr < aCount; aItr++) {
            int aItem = Integer.parseInt(scanner.nextLine().trim());
            a[aItr] = aItem;
        }

        double[] result = runningMedian(a);

        for (int resultItr = 0; resultItr < result.length; resultItr++) {
            bufferedWriter.write(String.valueOf(result[resultItr]));

            if (resultItr != result.length - 1) {
                bufferedWriter.write("\n");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();
    }
}

Pairs

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

public class Solution {

// Complete the pairs function below.
   static int pairs(int k, int[] arr) {
        HashSet<Integer> d = new HashSet<Integer>();
        for (int i = 0; i < arr.length; i++) {
            d.add(arr[i]);
        }
        int count = 0;
        for (int i : d) {
            if (d.contains(i + k)) {
                count++;
            }
        }
        return count;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nk = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nk[0]);

        int k = Integer.parseInt(nk[1]);

        int[] arr = new int[n];

        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int arrItem = Integer.parseInt(arrItems[i]);
            arr[i] = arrItem;
        }

        int result = pairs(k, arr);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Contacts

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

public class Solution {

// Alphabet size (# of symbols)
    static final int ALPHABET_SIZE = 26;

    // trie node
    static class TrieNode {
        TrieNode[] children = new TrieNode[ALPHABET_SIZE];
        int repeats;
        // isEndOfWord is true if the node represents
        // end of a word
        boolean isEndOfWord;

        TrieNode() {
            isEndOfWord = false;
            repeats = 1;
            for (int i = 0; i < ALPHABET_SIZE; i++)
                children[i] = null;
        }
    };

    static TrieNode root;

    // If not present, inserts key into trie
    // If the key is prefix of trie node,
    // just marks leaf node
    static void insert(String key) {
        int level;
        int length = key.length();
        int index;

        TrieNode pCrawl = root;

        for (level = 0; level < length; level++) {
            index = key.charAt(level) - 'a';
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();
            else
                pCrawl.children[index].repeats++;

            pCrawl = pCrawl.children[index];
        }

        // mark last node as leaf
        pCrawl.isEndOfWord = true;
    }

    // Returns true if key presents in trie, else false
    static int countInTrie(String key) {
        int level;
        int length = key.length();
        int index;
        TrieNode pCrawl = root;

        for (level = 0; level < length; level++) {
            index = key.charAt(level) - 'a';

            if (pCrawl.children[index] == null)
                return 0;

            pCrawl = pCrawl.children[index];
        }
        return pCrawl.repeats;
    }

    // }
    /*
     * Complete the contacts function below.
     */
    static int[] contacts(String[][] queries) {
        root = new TrieNode();
        ArrayList<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < queries.length; i++) {
            if (queries[i][0].equals("add")) {
                insert(queries[i][1]);
            } else if (queries[i][0].equals("find")) {
                res.add(countInTrie(queries[i][1]));
            }
        }
        int[] result = new int[res.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = res.get(i);
        }
        return result;
    }


    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int queriesRows = Integer.parseInt(scanner.nextLine().trim());

        String[][] queries = new String[queriesRows][2];

        for (int queriesRowItr = 0; queriesRowItr < queriesRows; queriesRowItr++) {
            String[] queriesRowItems = scanner.nextLine().split(" ");

            for (int queriesColumnItr = 0; queriesColumnItr < 2; queriesColumnItr++) {
                String queriesItem = queriesRowItems[queriesColumnItr];
                queries[queriesRowItr][queriesColumnItr] = queriesItem;
            }
        }

        int[] result = contacts(queries);

        for (int resultItr = 0; resultItr < result.length; resultItr++) {
            bufferedWriter.write(String.valueOf(result[resultItr]));

            if (resultItr != result.length - 1) {
                bufferedWriter.write("\n");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();
    }
}

Tree: Level Order Traversal

import java.util.*;
import java.io.*;

class Node {
    Node left;
    Node right;
    int data;
    
    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {

    /* 
    
    class Node 
        int data;
        Node left;
        Node right;
    */
    public static void levelOrder(Node root) {
        StringBuilder out = new StringBuilder();
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        
        while(!q.isEmpty()) {
            Node current= q.poll();
            out.append(current.data+" ");
            
            if(current.left != null) 
                q.add(current.left);
            
            if(current.right !=null)
                q.add(current.right);
            
        }
      
      System.out.println(out.toString());
      
      
    }

    public static Node insert(Node root, int data) {
        if(root == null) {
            return new Node(data);
        } else {
            Node cur;
            if(data <= root.data) {
                cur = insert(root.left, data);
                root.left = cur;
            } else {
                cur = insert(root.right, data);
                root.right = cur;
            }
            return root;
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        Node root = null;
        while(t-- > 0) {
            int data = scan.nextInt();
            root = insert(root, data);
        }
        scan.close();
        levelOrder(root);
    }   
}

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;
    }
}