Oct 16, 2024 · Oct 16, 2024
diff --git a/DesignDataStructure/designI.js b/DesignDataStructure/designI.js
    Frequency: Least frequent.
 */

 /*
 example:

 class effStructure {
  this.maxHeap = [];
 3) deleteMin(): O(log N)
 4) deleteMax(): O(log N)
 5) Insert(log N)
 6) Delete: O(log N)
 6) Delete: O(log N)
 */
diff --git a/Maximal_square.js b/Maximal_square.js
 var maximalSquare = function(matrix) {
  var m = matrix.length;
  var n = (matrix[0] || []).length;
  var dp = Array(m).fill(0).map(_ => Array(n));
  var dp = Array(m).fill(0).map(() => Array(n));
  var max = 0;

  for (var k = 0; k < m; k++) {
    dp[k][0] = matrix[k][0] ==='1' ? 1 : 0;
    dp[k][0] = matrix[k][0] ==="1" ? 1 : 0;
    max = Math.max(max, dp[k][0]);
  }

  for (var p = 0; p < n; p++) {
    dp[0][p] = matrix[0][p] ==='1' ? 1 : 0;
    dp[0][p] = matrix[0][p] ==="1" ? 1 : 0;
    max = Math.max(max, dp[0][p]);
  }

  for (var i = 1; i < m; i++) {
    for (var j = 1; j < n; j++) {
      if (matrix[i][j] ==='1') {
      if (matrix[i][j] ==="1") {
        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
        max = Math.max(max, dp[i][j]);
      } else {
  return max * max;

 };

 module.exports.maximalSquare = maximalSquare;
diff --git a/Maximal_square_Test.js b/Maximal_square_Test.js
 const assert = require('assert');
 const {Maximalsquare } = require('../LeetcodeProblems/Maximal_square');
 const assert = require("assert");
 const {Maximalsquare } = require("../LeetcodeProblems/Maximal_square");

 function test1() {
  var matrix = [
    [1, 0, 1, 0, 0],
    [1, 0, 1, 1, 1],
    [1, 1, 1, 1 1],
    [1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0],
  ]
  ];

  assert.strictEqual(Maximalsquare(matrix), 4);
 }
  var matrix = [
    [0, 1],
    [1,0]
  ]
  ];

  assert.strictEqual(Maximalsquare(matrix), 1);
 }

 function test3(){
  var matrix = [
    [0]
    ]
   assert.strictEqual(Maximalsquare(matrix), 0);
  ];

  assert.strictEqual(Maximalsquare(matrix), 0);
 }

 function test() {
  test3();
 }

 module.exports.test = test
 module.exports.test = test;
diff --git a/SortingAlgorithms/QuickSort.js b/SortingAlgorithms/QuickSort.js
 function swap(items, leftIndex, rightIndex){
 var temp = items[leftIndex];
 items[leftIndex] = items[rightIndex];
 items[rightIndex] = temp;
  var temp = items[leftIndex];
  items[leftIndex] = items[rightIndex];
  items[rightIndex] = temp;
 }
 function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], //middle element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //sawpping two elements
            i++;
            j--;
        }
  var pivot = items[Math.floor((right + left) / 2)], //middle element
    i       = left, //left pointer
    j       = right; //right pointer
  while (i <= j) {
    while (items[i] < pivot) {
      i++;
    }
    return i;
    while (items[j] > pivot) {
      j--;
    }
    if (i <= j) {
      swap(items, i, j); //sawpping two elements
      i++;
      j--;
    }
  }
  return i;
 }

 function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
  var index;
  if (items.length > 1) {
    index = partition(items, left, right); //index returned from partition
    if (left < index - 1) { //more elements on the left side of the pivot
      quickSort(items, left, index - 1);
    }
    if (index < right) { //more elements on the right side of the pivot
      quickSort(items, index, right);
    }
    return items;
  }
  return items;
 }

 module.exports.quickSort = quickSort;
diff --git a/SortingAlgorithms/heapSort.js b/SortingAlgorithms/heapSort.js
 // Testing Gist
 var heapSort = function(arr) {
  var n = arr.length;
  for(var i = Math.floor(n/2) - 1; i >= 0; i--)
  for(let i = Math.floor(n/2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  for(var i = n - 1; i >= 0; i--) {
  for(let i = n - 1; i >= 0; i--) {
    swap(arr, 0, i);
    heapify(arr, i, 0);
  }

  return arr;
 }
 };

 var heapify = function(arr, n, i) {
  var left = 2 * i + 1;
    swap(arr, i, right);
    heapify(arr, n, right);
  }
 }
 };

 var swap = function(arr, a, b) {
  var temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
 }
 };

 console.log(heapSort([14, 1, 10, 2, 3, 5, 6, 4, 7, 11, 12, 13]));
 console.log(heapSort([]));
 console.log(heapSort([1]));
 console.log(heapSort([2, 1]));
 console.log(heapSort([1,7,2,3,4,1,10,2,3,4,5]))
 console.log(heapSort([1,7,2,3,4,1,10,2,3,4,5]));

diff --git a/utilsClasses/ListNodeTestHelper.js b/utilsClasses/ListNodeTestHelper.js
 const assert = require('assert');
 const assert = require("assert");

 var assertList = function(list, expectedArr) {
  const listlength = list ? list.length() : 0;
    assert.strictEqual(list.val, expectedArr[i]);
    list = list.next;
  }
 }
 };

 module.exports.assertList = assertList;
Original file line number	Diff line number	Diff line change
Expand Up		@@ -21,6 +21,8 @@ The data structure should be efficient enough to accommodate the operations acco
		Frequency: Least frequent.
		*/

		/*
		example:

		class effStructure {
		this.maxHeap = [];
Expand All		@@ -33,4 +35,5 @@ class effStructure {
		3) deleteMin(): O(log N)
		4) deleteMax(): O(log N)
		5) Insert(log N)
		6) Delete: O(log N)
		6) Delete: O(log N)
		*/
Original file line number	Diff line number	Diff line change
Expand Up		@@ -25,22 +25,22 @@ Output: 0
		var maximalSquare = function(matrix) {
		var m = matrix.length;
		var n = (matrix[0] \|\| []).length;
		var dp = Array(m).fill(0).map(_ => Array(n));
		var dp = Array(m).fill(0).map(() => Array(n));
		var max = 0;

		for (var k = 0; k < m; k++) {
		dp[k][0] = matrix[k][0] ==='1' ? 1 : 0;
		dp[k][0] = matrix[k][0] ==="1" ? 1 : 0;
		max = Math.max(max, dp[k][0]);
		}

		for (var p = 0; p < n; p++) {
		dp[0][p] = matrix[0][p] ==='1' ? 1 : 0;
		dp[0][p] = matrix[0][p] ==="1" ? 1 : 0;
		max = Math.max(max, dp[0][p]);
		}

		for (var i = 1; i < m; i++) {
		for (var j = 1; j < n; j++) {
		if (matrix[i][j] ==='1') {
		if (matrix[i][j] ==="1") {
		dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
		max = Math.max(max, dp[i][j]);
		} else {
Expand All		@@ -52,3 +52,5 @@ var maximalSquare = function(matrix) {
		return max * max;

		};

		module.exports.maximalSquare = maximalSquare;
Original file line number	Diff line number	Diff line change
		@@ -1,13 +1,13 @@
		const assert = require('assert');
		const {Maximalsquare } = require('../LeetcodeProblems/Maximal_square');
		const assert = require("assert");
		const {Maximalsquare } = require("../LeetcodeProblems/Maximal_square");

		function test1() {
		var matrix = [
		[1, 0, 1, 0, 0],
		[1, 0, 1, 1, 1],
		[1, 1, 1, 1 1],
		[1, 1, 1, 1, 1],
		[1, 0, 0, 1, 0],
		]
		];

		assert.strictEqual(Maximalsquare(matrix), 4);
		}
Expand All		@@ -16,16 +16,17 @@ function test2() {
		var matrix = [
		[0, 1],
		[1,0]
		]
		];

		assert.strictEqual(Maximalsquare(matrix), 1);
		}

		function test3(){
		var matrix = [
		[0]
		]
		assert.strictEqual(Maximalsquare(matrix), 0);
		];

		assert.strictEqual(Maximalsquare(matrix), 0);
		}

		function test() {
Expand All		@@ -34,4 +35,4 @@ function test() {
		test3();
		}

		module.exports.test = test
		module.exports.test = test;
Original file line number	Diff line number	Diff line change
		@@ -1,39 +1,40 @@
		function swap(items, leftIndex, rightIndex){
		var temp = items[leftIndex];
		items[leftIndex] = items[rightIndex];
		items[rightIndex] = temp;
		var temp = items[leftIndex];
		items[leftIndex] = items[rightIndex];
		items[rightIndex] = temp;
		}
		function partition(items, left, right) {
		var pivot = items[Math.floor((right + left) / 2)], //middle element
		i = left, //left pointer
		j = right; //right pointer
		while (i <= j) {
		while (items[i] < pivot) {
		i++;
		}
		while (items[j] > pivot) {
		j--;
		}
		if (i <= j) {
		swap(items, i, j); //sawpping two elements
		i++;
		j--;
		}
		var pivot = items[Math.floor((right + left) / 2)], //middle element
		i = left, //left pointer
		j = right; //right pointer
		while (i <= j) {
		while (items[i] < pivot) {
		i++;
		}
		return i;
		while (items[j] > pivot) {
		j--;
		}
		if (i <= j) {
		swap(items, i, j); //sawpping two elements
		i++;
		j--;
		}
		}
		return i;
		}

		function quickSort(items, left, right) {
		var index;
		if (items.length > 1) {
		index = partition(items, left, right); //index returned from partition
		if (left < index - 1) { //more elements on the left side of the pivot
		quickSort(items, left, index - 1);
		}
		if (index < right) { //more elements on the right side of the pivot
		quickSort(items, index, right);
		}
		var index;
		if (items.length > 1) {
		index = partition(items, left, right); //index returned from partition
		if (left < index - 1) { //more elements on the left side of the pivot
		quickSort(items, left, index - 1);
		}
		if (index < right) { //more elements on the right side of the pivot
		quickSort(items, index, right);
		}
		return items;
		}
		return items;
		}

		module.exports.quickSort = quickSort;
Original file line number	Diff line number	Diff line change
		@@ -1,16 +1,17 @@
		// Testing Gist
		var heapSort = function(arr) {
		var n = arr.length;
		for(var i = Math.floor(n/2) - 1; i >= 0; i--)
		for(let i = Math.floor(n/2) - 1; i >= 0; i--) {
		heapify(arr, n, i);
		}

		for(var i = n - 1; i >= 0; i--) {
		for(let i = n - 1; i >= 0; i--) {
		swap(arr, 0, i);
		heapify(arr, i, 0);
		}

		return arr;
		}
		};

		var heapify = function(arr, n, i) {
		var left = 2 * i + 1;
Expand All		@@ -32,17 +33,17 @@ var heapify = function(arr, n, i) {
		swap(arr, i, right);
		heapify(arr, n, right);
		}
		}
		};

		var swap = function(arr, a, b) {
		var temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
		}
		};

		console.log(heapSort([14, 1, 10, 2, 3, 5, 6, 4, 7, 11, 12, 13]));
		console.log(heapSort([]));
		console.log(heapSort([1]));
		console.log(heapSort([2, 1]));
		console.log(heapSort([1,7,2,3,4,1,10,2,3,4,5]))
		console.log(heapSort([1,7,2,3,4,1,10,2,3,4,5]));
Original file line number	Diff line number	Diff line change
		@@ -1,4 +1,4 @@
		const assert = require('assert');
		const assert = require("assert");

		var assertList = function(list, expectedArr) {
		const listlength = list ? list.length() : 0;
Expand All		@@ -7,6 +7,6 @@ var assertList = function(list, expectedArr) {
		assert.strictEqual(list.val, expectedArr[i]);
		list = list.next;
		}
		}
		};

		module.exports.assertList = assertList;