DS4Fun

Given a non negative integer number num . For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array. Input: 2 Output: [0,1,1] Follow up: It is very easy to come up with a solution with run time  O(n*sizeof(integer)) . But can you do it in linear time  O(n)  /possibly in a single pass? Space complexity should be  O(n) . Can you do it like a boss? Do it without using any builtin function like  __builtin_popcount  in c++ or in any other language. Now, It is time to think before we write our code onto a paper. We read about the binary representation in college. A binary number is a special type of representation of a number in a binary format where the bit can be 0 or 1. You had an idea that the computer system also understands the 0's and 1's. 0's mean an inactive  bit and 1's mean an active bit. Let's understand the easiest way to calculate the number using the pic...

As we have already covered the singly linked list in our previous blog . Now, It's the right time to discuss the circular singly linked list which is nothing but our tail node is pointing to the head node. Here we are using a few buzz words like:- Node- It is an actual container that holds data along with the reference of the next node. Head Node- It is the starting node of a linked list, if somehow it's lost then the complete linked list will be lost. Tail Node- It represents the linked list last node. Now, let us understand the implementation of the circular singly linked list with the help of code. NOTE: - Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it  as an  Object. #1 Create a Custom Linked List  class Node< T > { T data ; Node next ; public Node( T data) { this . data = data; } } It's our generic implementation of a class, which can hold any type of ...

You are given a string containing characters A and B only. Your task is to change it into a string such that there are no matching adjacent characters. To do this, you are allowed to delete zero or more characters in the string. Your task is to find the minimum number of required deletions. For example, given the string s = AABAAB , remove an A at positions 0 and 3 to make s=ABAB in 2 deletions. Function Description Complete the alternatingCharacters function in the editor below. It must return an integer representing the minimum number of deletions to make the alternating string. alternatingCharacters has the following parameter(s): s: a string Input Format The first line contains an integer  q , the number of queries. The next lines q each contain a string s . Constraints 1 <= q <= 10 1 <= |s| <= 10 5 Each string s will consist only of characters A and B. Output Format For each query, print the minimum number of deletions required on...

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 t...

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 pe...

Given a positive integer num, write a function that returns True if num is a perfect square else False. Note: Do not use any built-in library function such as sqrt. Example 1: Input: 16 Output: true Binary Search Approach - O(log n) public boolean isPerfectSquare( int num) { long left = 1 ; long right = num; while (left<= right) { long mid = left + (right -left) / 2 ; if (mid * mid == num) return true ; if (mid * mid < num) { left = mid + 1 ; } else right = mid - 1 ; } return false ; } Square Root Approach - O(sqrt(n)) We have observed the equation and find some similarities, let's discuss with an example. Input: 16 1 + 3 + 5 + 7 = 16 So 1 + 3 + 5 + 7 + 9 + 11 + ... + (2n -1) = (2(n-1) + 1) n/2  = n*n public boolean isPerfectSquare( int num) { int i = 1 ; while (num > 0 ) { num -= i; i += 2 ; } return num == 0 ; }

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 the singly linked list in a deep-dive. NOTE: - Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it  as an  Object. #1 Create a Custom Node class Node< T > { T data ; Node next ; public Node( T data) { this . data = data; } } It is our generic custom linked list implementation, which holds the value of any type and the address of the next node. #2 Create Custom Singly Linked List-O(1) public class CustomLinkedList< T > { Node< T > head , tail ; int size = 0 ; } Here, we will store the start and last address reference along with the number of elements in the Linked List. #3 Adding Node at the end-O(1) /** * Inserting element at the last position * Time/Space Complexity - O(1) * @param value */ public void add( T value) { Node< T > node = new Node<>(value); size ++; if ( head == null ) { ...

A linked list is a linear data structure and stores it at the non-contiguous memory location. Non-contiguous memory location means that it doesn't guarantee that each data element will reside next to each other in the memory. There are chances that one memory location address is 1000 and another one is 1200; then the immediate question comes into our mind. How do they actually know which data will be next? Are they using some kind of magic behind the scene? Let's understand the linked list with the  carousel/slider example which we used many times on many websites. You have analyzed the carousel and are working on the number of images that put it into some sequence and rotate one by one. They have one common characteristic, that is, if we want to look for the last image in the carousel then we have to go one by one till the last. There is one start point, which we usually call  head and one termination point which we usually call a tail . Each Image can be considered as a n...