DS4Fun

An  image  is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535). Given a coordinate  (sr, sc)  representing the starting pixel (row and column) of the flood fill, and a pixel value  newColor , "flood fill" the image. To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor. At the end, return the modified image. Input: image = [[1,1,1],[1,1,0],[1,0,1]] sr = 1, sc = 1, newColor = 2 Output: [[2,2,2],[2,2,0],[2,0,1]] Explanation: From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected by a path of the same color as the starting pixel are colored with the new color. Note the b

In a town, there are  N  people labeled from  1  to  N .  There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: The town judge trusts nobody. Everybody (except for the town judge) trusts the town judge. There is exactly one person that satisfies properties 1 and 2. You are given  trust , an array of pairs  trust[i] = [a, b]  representing that the person labeled  a  trusts the person labeled  b . If the town judge exists and can be identified, return the label of the town judge.  Otherwise, return  -1 . Input: N = 4 , trust = [[1,3],[1,4],[2,3],[2,4],[4,3]] Output: 3 Let's understand the problem, we have an array of people where the 0th index person will trust the 1st index person. Any person with maximum trust N - 1 will be town judge and return the label if not then return -1. In the above input of trust, 1st person is trusting on 3rd and 4th person. Each person has a judge count and it will increase if a person t

Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1. s = "leetcode" return 0. s = "loveleetcode", return 2. Note: You may assume the string contains only lowercase letters. Quadratic Algorithm Time Complexity- O(n 2 ) & Space Complexity - O(1) public static int firstUniqChar(String s) { int length = s.length(), count = 0 ; for ( int i = 0 ; i < length; i++) { count = 0 ; for ( int j = 0 ; j < length; j++) { if (s.charAt(i) == s.charAt(j)) { count++; if (count > 1 ) break ; } } if (count == 1 ) return i; } return - 1 ; } Quadratic  Algorithm Time Complexity - O( n 2 ) & Space Complexity - O(n) public static int firstUniqChar(String s) { char [] chars = s.toCharArray(); Arrays. sort (chars); String sortedString = new String(chars)

Let's do the implementation and understand it in a deep-dive. We will go step-by-step and implement the most useful method. Declare and Initialization Phase- O(1) private int currentRow = 0 ; private int currentColumn = 0 ; private int maxRow , maxColumn ; private int [][] nums ; private int maxElement ; public MultiDimensionArray( int maxRow, int maxColumn) { this . maxRow = maxRow; this . maxColumn = maxColumn; nums = new int [maxRow][maxColumn]; maxElement = maxRow*maxColumn; } Add Element- O(1) public void add( int value) { if (size() <= maxElement ) { if ( currentColumn <= maxColumn - 1 ) { nums [ currentRow ][ currentColumn ++] = value; } else { if ( currentRow < maxRow - 1 ) { currentRow ++; currentColumn = 0 ; } nums [ currentRow ][ currentColumn ++] = value; } } else throw new ArrayIndexOutOfBoundsException(); } Update th

Let's do the implementation and understand it in a deep-dive. We will go step-by-step and implement the most useful method. Declare and Initialization Phase- O(1) int [] nums ; int maxCapacity ; int size = 0 ; public Array( int maxCapacity) { this . maxCapacity = maxCapacity; nums = new int [maxCapacity]; } Add Element- O(1) private void add( int value) { if ( size < maxCapacity ) { nums [ size ++] = value; } else throw new ArrayIndexOutOfBoundsException( size ); } Add Element in a particular and shift all the elements to the right- O(n) private void add( int index, int value) { if ( size < maxCapacity && index > 0 ) { int tempIndex = size ; while (tempIndex > index) { nums [tempIndex] = nums [--tempIndex]; } nums [index] = value; size = (index > size ) ? index + 1 : size + 1 ; } else throw new ArrayIndexOutOfBoundsException(); } Update the element v

An array is a collection of homogenous data stored at the contiguous memory locations. Each element is uniquely identified by its index value. An array is of a fixed size, once it is initialized with a number of an element is allowed then it won't add more than it's capacity. Let's analyze the problem when we come up with this solution. Supposedly, you have to declare and initialize the same data type multiple variables in a program. What do you think, how easy could it be to remember all the names? To overcome these types of problems, we came with the solution of an array. There are two types of array. Single Dimension Array Multi Dimension Array 2D Array 3D Array and so on. Java supports 255 D Array but in actual we mainly focus on 1D and 2D Array. One-Dimension Array (1D Array) 1D Array conceptually means that you have a single row with multiple columns and each column has the same size and they are contiguous by nature. In the example below, you can cle

Cache Replacement FIFO Algorithm - (First In First Out) Before, we understood how the cache replacement algorithm works using FIFO. We will just look for a while to understand the FIFO with the layman term. Suppose a company running a seminar and max capacity of the seminar hall is 100 employees. They have decided whoever comes first they will get the entry and once's seminar hall is full then wouldn't allow anyone. There is no priority to anyone or any designation. So, we will implement a cache replacement algorithm using the Queue abstract data type. We can implement a queue using ArrayList or LinkedList. Let's do the code and understand the implementation of the algorithm. Implement Cache Replacement FIFO policy using ArrayList import java.util.Arrays; import java.util.List; import java.util.Optional; /** * @author Chandra Shekhar Paatni on 26/04/20 */ public class CacheReplacementFIFO< T > { T [] cacheReplacementFIFOS ; int index = - 1 ; pu

We are now solving a problem which is asked by many of the product based companies. They always want you to give a proper solution with all edge cases covered.However, an array sorted in ascending is rotated (i.e., [0,1,2,3,4,5,6,7] might become [4,5,6,7,0,1,2,3]). Constraints No duplicate element in an array. Runtime complexity must be in the order of O(log n). If found then return index otherwise return -1. Example 1: Input: nums = [4,5,6,7,0,1,2], searchElement = 0 Output: 4 Linear Search Solution- O(n) time complexity It comes to our mind easily to check each element of an array until it finds it or till the array reaches the end of the index. class Solution { public static void main(String[] args) { System. out .println( search ( new int []{ 4 , 5 , 6 , 7 , 0 , 1 , 2 }, 0 )); } public static int search( int [] nums, int searchElement) { if (nums. length != 0 ) { for ( int i = 0 ; i < nums. length ; i++) {