Median of A Row Wise Sorted Matrix

PHOTO

Tue Feb 08 2022 08:02:14 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #lecture #2d #array #matrix #median #rowwisesorted

// Time Complexity : O(r * log(max - min) * logC)

import java.util.Arrays;

public class MedianInRowSorted
{
    static public int matMed(int mat[][], int r ,int c)
    {
    	int min = mat[0][0], max = mat[0][c-1];
    	for (int i=1; i<r; i++)
    	{
    		if (mat[i][0] < min)
    			min = mat[i][0];
    
    		if (mat[i][c-1] > max)
    			max = mat[i][c-1];
    	}
    
    	int medPos = (r * c + 1) / 2;
    	while (min < max)
    	{
    		int mid = (min + max) / 2;
    		int midPos = 0;
            int pos = 0;
    		for (int i = 0; i < r; ++i){
    			    pos = Arrays.binarySearch(mat[i],mid);
                    
                    if(pos < 0)
                        pos = Math.abs(pos) - 1;
                      
                    
                    else
                    {
                        while(pos < mat[i].length && mat[i][pos] == mid)
                            pos += 1;
                    }
                      
                    midPos = midPos + pos;
    		}
    		if (midPos < medPos)
    			min = mid + 1;
    		else
    			max = mid;
    	}
    	return min;
    }

    public static void main(String[] args)
    {
    	int r = 3, c = 5;
    	int m[][]= { {5,10,20,30,40}, {1,2,3,4,6}, {11,13,15,17,19} };
    	System.out.println("Median is " + matMed(m, r, c)); 
    	
    }
}

COPY

Input : 1 10 20 15 25 35 5 30 40 Output : 20 // 1, 5, 10, 15, 20, 25, 30, 35, 40 ^ | Input : 2 4 6 8 10 1 3 5 7 9 100 200 400 500 800 Output : 8 // 1, 2, 3, 5, 6, 7, 8, 9, 10, 100, 200, 400, 500, 800 ^ |

Save snippets that work from anywhere online with our extensions

Comments

Matrix

@Uttam

Print a Matrix in Snake Pattern Print Boundary Elements - Matrix Boundary Traversal Transpose of a Matrix Rotate Matrix Anti-clockwise by 90 Spiral Traversal of Matrix Search in Row-wise and Column-wise sorted matrix Median of A Row Wise Sorted Matrix Adding two matrices Sum of upper and lower triangles Multiply the matrices Determinant of a Matrix Exchange matrix columns Reversing the columns of a Matrix Interchanging the rows of a Matrix Boolean Matrix Make Matrix Beautiful

#java #howto #interviewquestions #mobile

How to use Java Swing to create a button

import javax.swing.*;  
public class FirstSwingExample {  
public static void main(String[] args) {  
JFrame f=new JFrame();//creating instance of JFrame  
          
JButton b=new JButton("click");//creating instance of JButton  
b.setBounds(130,100,100, 40);//x axis, y axis, width, height  
          
f.add(b);//adding button in JFrame  
          
f.setSize(400,500);//400 width and 500 height  
f.setLayout(null);//using no layout managers  
f.setVisible(true);//making the frame visible  
}  
}

#java #java #arraylists #while-loops #equala

How to insert ArrayList into While-condition?

List<String> songList = new ArrayList<>();
songList.add("Some song"); //Repeat until satisfied

System.out.println("\n\tWelcome! Please choose a song!");
String songChoice = scan.nextLine();
while (!songList.contains(songChoice)) {
    //Do stuff when input is not a recognised song
}

#java #gfg #geeksforgeeks #lecture #recursion #rope cutting

Rope Cutting Problem

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

class GFG 
{
	static int maxCuts(int n, int a, int b, int c)
	{
		if(n == 0) return 0;
		if(n < 0)  return -1;

		int res = Math.max(maxCuts(n-a, a, b, c), 
		          Math.max(maxCuts(n-b, a, b, c), 
		          maxCuts(n-c, a, b, c)));

		if(res == -1)
			return -1;

		return res + 1; 
	}
  
    public static void main(String [] args) 
    {
    	int n = 5, a = 2, b = 1, c = 5;
    	
    	System.out.println(maxCuts(n, a, b, c));
    }
}

#java #gfg #geeksforgeeks #arrays #practice #frequencycount #frequencies #limitedrange

Frequencies of Limited Range Array Elements

class Solution{
    //Function to count the frequency of all elements from 1 to N in the array.
    public static void frequencyCount(int arr[], int N, int P)
    {
        //Decreasing all elements by 1 so that the elements
        //become in range from 0 to n-1.
        int maxi = Math.max(P,N);
        int count[] = new int[maxi+1];
        Arrays.fill(count, 0);
        for(int i=0;i<N;i++){
            count[arr[i]]++; 
        }
        
        for(int i=0;i<N;i++){
            arr[i] = count[i+1];
        }
    }
}

#java

Print Nested Array in Java

String[][] deepArray = new String[][] {{"John", "Mary"}, {"Alice", "Bob"}};
System.out.println(Arrays.toString(deepArray));
//output: [[Ljava.lang.String;@106d69c, [Ljava.lang.String;@52e922]
System.out.println(Arrays.deepToString(deepArray));

#java

How to efficiently iterate over each entry in a Java Map

Map<String, String> map = ...
for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "/" + entry.getValue());
}

#java #interviewquestions #search

How to binary search in Java

import java.util.Stack;

/**
 * Java Program to implement a binary search tree. A binary search tree is a
 * sorted binary tree, where value of a node is greater than or equal to its
 * left the child and less than or equal to its right child.
 * 
 * @author WINDOWS 8
 *
 */
public class BST {

    private static class Node {
        private int data;
        private Node left, right;

        public Node(int value) {
            data = value;
            left = right = null;
        }
    }

    private Node root;

    public BST() {
        root = null;
    }

    public Node getRoot() {
        return root;
    }

    /**
     * Java function to check if binary tree is empty or not
     * Time Complexity of this solution is constant O(1) for
     * best, average and worst case. 
     * 
     * @return true if binary search tree is empty
     */
    public boolean isEmpty() {
        return null == root;
    }

    
    /**
     * Java function to return number of nodes in this binary search tree.
     * Time complexity of this method is O(n)
     * @return size of this binary search tree
     */
    public int size() {
        Node current = root;
        int size = 0;
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || current != null) {
            if (current != null) {
                stack.push(current);
                current = current.left;
            } else {
                size++;
                current = stack.pop();
                current = current.right;
            }
        }
        return size;
    }


    /**
     * Java function to clear the binary search tree.
     * Time complexity of this method is O(1)
     */
    public void clear() {
        root = null;
    }

}

#java #java #2dchar array

How do you check a row in a 2D char array for a specific element and then count how many of that element are in the row? (Java)

private boolean oneQueenPerRow() {
    int foundQueens;
    for (int i = 0; i < board.length; i++) {
        foundQueens = 0;//each loop is a checked row
        for (int j = 0; j < board.length; j++) {
            if (board[i][j] == QUEEN)
                foundQueens++;
        }
        if (foundQueens > 1) return false;
    }
    return true;
}

#java

Finding all classes implementing a specific interface

public <T> List<Class<? extends T>> findAllMatchingTypes(Class<T> toFind) {
    foundClasses = new ArrayList<Class<?>>();
    List<Class<? extends T>> returnedClasses = new ArrayList<Class<? extends T>>();
    this.toFind = toFind;
    walkClassPath();
    for (Class<?> clazz : foundClasses) {
        returnedClasses.add((Class<? extends T>) clazz);
    }
    return returnedClasses;
}

#java #mathematics #gfg #geeksforgeeks #quadraticequationroots

Quadratic Equation Roots

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

class Solution {
    public ArrayList<Integer> quadraticRoots(int a, int b, int c) {
        
       ArrayList<Integer> numbers = new ArrayList<Integer>();
       int d = (int) (Math.pow(b,2)-(4*a*c));
       int r1 = (int) Math.floor(((-1*b)+Math.sqrt(d))/(2*a));
       int r2 = (int) Math.floor(((-1*b)-Math.sqrt(d))/(2*a));
       if(d<0){
           numbers.add(-1);
       }
       else
       {
           numbers.add(Math.max(r1,r2));
           numbers.add(Math.min(r1,r2));
       }
       return numbers;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int a, b, c;
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();
            Solution obj = new Solution();
            ArrayList<Integer> ans = obj.quadraticRoots(a, b, c);
            if (ans.size() == 1 && ans.get(0) == -1)
                System.out.print("Imaginary");
            else
                for (Integer val : ans) System.out.print(val + " ");
            System.out.println();
        }
    }
}

#java #gfg #geeksforgeeks #recursion #possiblewordsfrom phone digits

Possible Words From Phone Digits

class Solution
{
    // String array to store keypad characters
    static String hash[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    //Function to find list of all words possible by pressing given numbers.
    static ArrayList <String> possibleWords(int a[], int N)
    {
        String str = "";
        for(int i = 0; i < N; i++)
        str += a[i];
        ArrayList<String> res = possibleWordsUtil(str);
        //arranging all possible strings lexicographically.
        Collections.sort(res); 
        return res;
                    
    }
    
    //recursive function to return all possible words that can
    //be obtained by pressing input numbers.  
    static ArrayList<String> possibleWordsUtil(String str)
    {
        //if str is empty 
        if (str.length() == 0) { 
            ArrayList<String> baseRes = new ArrayList<>(); 
            baseRes.add(""); 
  
            //returning a list containing empty string.
            return baseRes; 
        } 
        
        //storing first character of str
        char ch = str.charAt(0); 
        //storing rest of the characters of str 
        String restStr = str.substring(1); 
  
        //getting all the combination by calling function recursively.
        ArrayList<String> prevRes = possibleWordsUtil(restStr); 
        ArrayList<String> Res = new ArrayList<>(); 
      
        String code = hash[ch - '0']; 
  
        for (String val : prevRes) { 
  
            for (int i = 0; i < code.length(); i++) { 
                Res.add(code.charAt(i) + val); 
            } 
        } 
        //returning the list.
        return Res; 
    }
}

#android #java #xml

Android LinearLayout gradient background

<?xml version="1.0" encoding="utf-8"?>
<shape xmlns:android="http://schemas.android.com/apk/res/android">
    <gradient
        android:angle="45"
        android:startColor="#ff00ff"
        android:endColor="#000000"/>
</shape>

> More steps

#java

Its just print some message on console

for(int i = 0; i < 108; i++) {
System.out.println('Jai Shri Ram!');
}

#android #java

Intent to Start New Activity in Android Studio

// IntendedActivity - the file you wish to open
// CurrentActivity - the file where this code is placed  

Intent intent = new Intent (this, IntendedActivity.class);
    CurrentActivity.this.startActivity(intent);

#java

Insertion Sort in Java

 public void sort(int array[]) { 
     for (int i = 1; i < array.length; i++) { 
          int key = array[i]; 
          int j = i - 1; 
          while (j >= 0 && array[j] > key) { 
              array[j + 1] = array[j]; 
              j = j - 1; 
          } 
          array[j + 1] = key; 
      } 
 }

> More steps

Median of A Row Wise Sorted Matrix

Save snippets that work from anywhere online with our extensions

Comments

More like this

Matrix

Browse more snippets >>

Median of A Row Wise Sorted Matrix

Save snippets that work from anywhere online with our extensions

Comments

More like this

Matrix

Browse more snippets >>

Embed code snippet