Posts

Sliding Window Maximum (Maximum of all subarrays of size k) - Java Solution - Leetcode 239

Image
Solution approach : We will be using sliding window. Deque will be used to store useful element of current subarray. Add first element to deque. Then for adding next element, check if earlier elements are smaller, then remove all elements from deque. Maximum will always be at front of deque. For sliding and removing, check if arr[i] == front of queue, then remove the element. import java.util.Arrays ; import java.util.Deque ; import java.util.LinkedList ; public class MaxOfAllSubarrays { private static int [] findMaxOfAllSubArrays ( int [] arr , int subArraySize) { int [] answerArr = new int [arr. length - subArraySize + 1 ] ; int i = 0 , j = 0 , count = 0 ; Deque<Integer> deque = new LinkedList<>() ; while (j < arr. length ) { while (!deque.isEmpty() && deque.getLast() < arr[j]) deque.removeLast() ; deque.add(arr[j]) ; if (j - i + 1 == subArraySize) { answe...
Post a Comment
Read more

Find All Anagrams in a String - Java Solution (Leetcode - 438)

Image
We would be solving this problem using  Sliding Window approach with 1 Hashmap First we will populate pattern map with occurrence of chars in pattern map. Additionally, a new indicator distinctCharsInMapValueMoreThanZero will be created. It's initial value would be map.size(). This variable is for numbers of chars in map with value > 0. This will ensure we don't have to compare all values of map to see, if all characters are zero or not. When variable distinctCharsInMapValueMoreThanZero is zero, it means current substring is anagram of pattern.  When traversing string via Sliding window, we will keep reduce count of character in pattern map. In map, we will not push any char, which are not part of pattern.
Post a Comment
Read more

Count occurrence of anagrams in String

Image
We would be solving this problem using  Sliding Window approach with 1 Hashmap First we will populate pattern map with occurrence of chars in pattern map. Additionally, a new indicator distinctCharsInMapValueMoreThanZero will be created. It's initial value would be map.size(). This variable is for numbers of chars in map with value > 0. This will ensure we don't have to compare all values of map to see, if all characters are zero or not. When variable  distinctCharsInMapValueMoreThanZero is zero, it means current substring is anagram of pattern.  When traversing string via Sliding window, we will keep reduce count of character in pattern map. In map, we will not push any char, which are not part of pattern.
Post a Comment
Read more

First Negative Number in every Window of Size K (Java Solution)

  There are 3 approach to solve this problem : Brute Force  Time complexity - O (nk) Using list to store element with sliding window approach Time complexity - O(n) Auxiliary space - O(k)  Using sliding window approach without list By traversing array from reverse. Time complexity - O(n)
Post a Comment
Read more

Maximum Sum Subarray of Size K

 There are 2 approaches to handle this problem : Brute force way Optimized approach is via using Sliding Window. public class MaxSumSubArray {     //Driver program public static void main(String[] args) { int []arr = {2,3,5,2,9,7,1}; int subArraySize = 3; System.out.println(calcMaxSumSubArrayBruteForce(arr, subArraySize)); System.out.println(calcMaxSumSubArraySlidingWindow(arr, subArraySize)); } private static int calcMaxSumSubArrayBruteForce (int[] arr, int subArraySize) { int maxSum = 0; for (int i = 0; i <=arr.length-subArraySize ; i++) { int currentSum = 0; for (int j = i; j < i+subArraySize; j++) { currentSum += arr[j]; } if(currentSum > maxSum) maxSum = currentSum; } return maxSum; } private static int calcMaxSumSubArraySlidingWindow (int[] arr, int subArraySize) { int maxSum=Inte...
Post a Comment
Read more

ACID Properties in DBMS

Image
A Transaction  is a single logical unit of work which accesses and possibly modifies the contents of a database. Transactions access data using read and write operations.  In order to maintain consistency in a database, before and after the transaction, certain properties are followed. These are called  ACID  properties.    Atomicity   By this, we mean that either the entire transaction takes place at once or doesn’t happen at all. There is no midway i.e. transactions do not occur partially. Each transaction is considered as one unit and either runs to completion or is not executed at all. It involves the following two operations.  — Abort : If a transaction aborts, changes made to database are not visible.  — Commit : If a transaction commits, changes made are visible.  Atomicity is also known as the ‘All or nothing rule’.    Consider the following transaction  T  consisting of  T1  and  T2 : Transfer ...
Post a Comment
Read more
 Shell Sort Implementation program in Java https://github.com/cbsingh1/DailyCodingProblems/blob/main/src/main/java/com/cbsingh/sorting/ShellSortImpl.java
Post a Comment
Read more