Dutch national flag problem in Javascript

Image
Dutch national flag problem and solution in Javascript Problem statement:   The Dutch national flag (DNF) problem is one of the most popular programming problems proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors: white, red, and blue. The task is to randomly arrange balls of white, red, and blue such that balls of the same color are placed together. Now, let's consider an array with 3 distinct values say 0, 1 and 2. We won't be using any sort method and we need to sort this array in 0(n). Input Array :  let   arr  = [ 0 ,  2 ,  1 ,  0 ,  1 ,  2 ,  0 ,  2 ]; Expected Output: [ 0, 0, 0, 1, 1, 2, 2, 2 ] Solution Approach : When we see expected output, we can clearly see that sorted array is divided into 3 sections having values 0 , 1 and 2. So, let's divide the array in 3 sections: a) from 0th index to left boundary b) from left boundary to right boundary c) from right boundary to last index. Now we...
Post a Comment

Diagonal Traversal of Matrix in Javascript

Diagonal Traversal of Matrix/2D Array in Javascript

Problem statement: 

In this post, we will traverse a given matrix/2D array diagonally (from center to top right corner). Refer below attached diagram for better understanding.

Diagonal pattern:

Expected Output:

expected output :
    1
    6
    11
    16
    2
    7
    12
    3
    8
    4

Input Matrix: 

let input2DArray = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16],
];


Solution Approach :

 When we think about the pattern required, we can confirm that there will always be n number of diagonals that we will be traversing, that means the outer loop will be from 0 to n-1. 

I have added below diagram for a matrix n x n:

Inner loop will be having 2 variables i and j as row and col of matrix. we can see that row index=i in each iteration starts from zero and j will start from the index= diagonal.


Let's write the code now:

let n = input2DArray.length;

for (let diag = 0; diag < n; diag++) {
// this loop will go from 0 to n-1, 
// that is for each diagonal as shown in diagram.

  for (let i = 0, j = diag; j < n && i < n; j++, i++) {
    // i is always starting with 0 
    // but j will start with index equals to diag.

    console.log(input2DArray[i][j]);
  }
}

Output:
1 6 11 16 2 7 12 3 8 4

 


Comments

Post a Comment

Popular posts from this blog

Ice Cream Parlor : Hackerrank Problem and Solution

Ice Cream Parlor : Hackerrank Problem  Each time Sunny and Johnny take a trip to the Ice Cream Parlor, they pool together   dollars for ice cream. On any given day, the parlor offers a line of   flavors. Each flavor,  , is numbered sequentially with a unique ID number from   to   and has a cost,  , associated with it. Given the value of   and the cost of each flavor for   trips to the Ice Cream Parlor, help Sunny and Johnny choose two flavors such that they spend their entire pool of money ( ) during each visit. For each trip to the parlor, print the ID numbers for the two types of ice cream that Sunny and Johnny purchase as two space-separated integers on a new line. You must print the smaller ID first and the larger ID second. Note:  Two ice creams having unique IDs   and    may  have the same cost (i.e.,  ). Input Format The first line contains an in...
Read more

Disemvowel Trolls || Codewars problem and solution in Javascript || Topic : Strings and RegEx

  Problem: Disemvowel Trolls Description : Trolls are attacking your comment section! A common way to deal with this situation is to remove all of the vowels from the trolls' comments, neutralizing the threat. Your task is to write a function that takes a string and return a new string with all vowels removed. For example, the string "This website is for losers LOL!" would become "Ths wbst s fr lsrs LL!".   Solution 1# function disemvowel(str) {   var str = str.replace(/a/gi,'').replace(/e/gi,'').replace(/i/gi,'').replace(/o/gi,'').replace(/u/gi,'');   return str; } Solution 2# (slightly more concise) function disemvowel(str) {   return str.replace(/[aeiou]/gi, ''); }
Read more

Descending Order || CodeWars Problem and solution in javascript.

  Problem : Descending Order Description : Your task is to make a function that can take any non-negative integer as a argument and return it with its digits in descending order. Essentially, rearrange the digits to create the highest possible number. Examples : Input: 42145 Output: 54421 Input: 145263 Output: 654321 Input: 123456789 Output: 987654321     Solution 1# function descendingOrder(n){     var stringNumber = n.toString();   var arr = stringNumber.split('');   var result = arr.sort(function(a, b){return b - a});   var stringresult = result.join();   stringresult= stringresult.replace(/,/g,"");   return parseInt(stringresult) }   Solution 2# (slightly more concise) function descendingOrder(n){   return parseInt(String(n).split('').sort().reverse().join('')) }
Read more