5. Sorting a Matrix

-

5. Sorting a Matrix


Problem link :- click here


package progams;

import java.util.Arrays;
import java.util.Scanner;

public class Matrix__5
{
	/*
	    Given an NxN matrix. we have to sort all the elements of the matrix
	    		also given that     	time complexity :-  O( N^2 log(N) )
	    		and 				space complexity :- O( N^2 )
	    
	    so we can just store all the elements in an array
	    and sort that array (you can use quick sort or merge sort)
	    		but time complexity of quick and merge sort would be  O(N^2      log(N^2)  )     right?
	    													      O(N^2     2 log(N)    )
	    													      O(N^2      log(N)      )
	    			because we neglect constants while writing time complexity in O
	    and at last update the matrix
	*/
	
	static void sortMatrix(int mat[][], int n)
	{
		int i, j;
		int temp[] = new int[n*n];
		
		int k = 0;
		for(i=0; i<n; i++)
			for(j=0; j<n; j++)
				temp[k++] = mat[i][j];
		
		Arrays.sort(temp);
		
		k = 0;
		for(i=0; i<n; i++)
			for(j=0; j<n; j++)
				mat[i][j] = temp[k++];
		
	}
	
	public static void main(String[] args)
	{
		int i, j, r, c;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the number of rows : ");
		r = s.nextInt();
		System.out.print("Enter the numvber of columns : ");
		c = s.nextInt();
		int matrix[][] = new int[r][c];
		System.out.println("Enter the elements of the matrix : ");
		for(i=0; i<r; i++)
		{
			for(j=0; j<c; j++)
				matrix[i][j] = s.nextInt();
		}
		System.out.println("Given matrix : ");
		printMatrix(matrix, r, c);

		sortMatrix(matrix, r);
		System.out.println("\nMatrix after sorting : ");
		printMatrix(matrix, r, c);
	}

	static void printMatrix(int mat[][], int r, int c)
	{
		for(int i=0; i<r; i++)
		{
			for(int j=0; j<c; j++)
				System.out.print(mat[i][j] + "  ");
			System.out.println();
		}
	}
}

Time complexity :- O( n2 log(n) )
Space complexity :- O( n2 )

Comments

Post a Comment

Popular posts from this blog

4.Sort an array of 0's, 1's & 2's.

-
Image
4.Sort an array of 0's, 1's & 2's. Problem link :- click here C code #include<stdio.h> void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } void sort_012(int A[], int n) { int i, j, m; i = 0; j = n-1; m = 0; while(m<=j) { if(A[m] == 0) { swap(&A[i], &A[m]); i++; m++; } else if(A[m] == 1) { m++; } else { swap(&A[j], &A[m]); j--; } } } void main() { int arr[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array(only 0, 1, or 2)\n"); for(i=0; i<n; i++) scanf("%d",&arr[i]); printf("Given Array\n"); for(i=0; i<n; i++) printf("\t%d",arr[i]); printf("\n...
Read more

1. Reverse

-
Image
1. Reverse the Array.   Problem link :- Reverse the array Algorithm idea :- C code //Reverse the array #include<stdio.h> void rev_arr(int arr[], int start, int end) { int temp; while(start < end) { temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } void print_arr(int arr[], int size) { int i; for(i=0; i<size; i++) printf("\t%d",arr[i]); printf("\n"); } void main() { int arr1[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array\n"); for(i=0; i<n; i++) scanf("%d",&arr1[i]); printf("Array before reversing\n"); print_arr(arr1, n); rev_arr(arr1, 0, n-1); printf("\nArray after reversing\n"); print_arr(arr1, n); } Java code //Reverse the array package programs;...
Read more

3. Height of Binary tree

-
3. Height of Binary tree Problem link :- click here package Binary_Tree; public class BinaryTree__3 { static int heightOfTree(Node root) { if(root == null) return 0; int left_height = heightOfTree(root.left); int right_height = heightOfTree(root.right); return Math.max(left_height, right_height) + 1; } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); int arr[] = {2, -1, 3, -1, -1, 3}; tree.root = tree.createTree(arr, 0); int ans = heightOfTree(tree.root); System.out.println("Height : " + ans); } } Time complexity :- O(n) Space complexity :- O(n)
Read more