Today I have solved the problem in javascript

 Describe an algorithm to compute the longest increasing subsequence of an array of numbers in O(n log n) time.

const array = [10, 22, 9, 33, 21, 50, 41, 60, 80];
const lis = longestIncreasingSubsequence(array);
function longestIncreasingSubsequence(arr) {
  const piles = [];
  arr.forEach((num) => {
    let pileIndex = binarySearch(piles, num);
if (pileIndex === piles.length) {
      piles.push([num]);
    } else {
      piles[pileIndex].push(num);
    } });
return piles.reduce((maxPile, currentPile) => (currentPile.length > maxPile.length ? currentPile : maxPile), []);}
function binarySearch(piles, num) {
  let low = 0;
  let high = piles.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    if (piles[mid][piles[mid].length - 1] < num) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return low;
}
console.log(lis);


Comments

Post a Comment

Popular posts from this blog

Building a Full-Stack Student Management System with React.js and NestJS

  🚀 My Journey Creating a Student Management System 🌟 I'm excited to share my recent project — a Student Management System ! This project gave me hands-on experience in building a full-stack application, enhancing both my frontend and backend development skills. 💡 Project Overview The Student Management System is designed to help educational institutions efficiently manage student data, including enrollment, attendance, and performance. The goal was to create a user-friendly platform for both students and administrators. 🔨 Tech Stack Used ✅ Frontend: JavaScript, HTML, CSS, React.js ✅ Backend: TypeScript, NestJS, Node.js ✅ Database: MongoDB (with _id for unique identifiers) 🌟 Key Features ✔️ Student Registration – Easy registration with unique ID management ✔️ Attendance Tracking – Real-time updates on student attendance ✔️ Performance Reports – Generate and view student performance reports ✔️ Admin Panel – Secure access for administrators to manage student...
Read more

Today I have solved the problem in javascript

 Consider the following scenario: there are N mice and N holes placed at integer points along a line. Given this, find a method that maps mice to holes such that the largest number of steps any mouse takes is minimized.Each move consists of moving one mouse one unit to the left or right, and only one mouse can fit inside each hole.For example, suppose the mice are positioned at [1, 4, 9, 15], and the holes are located at [10, -5, 0, 16]. In this case, the best pairing would require us to send the mouse at 1 to the hole at -5, so our function should return 6. const mice = [1, 4, 9, 15]; const holes = [10, -5, 0, 16]; function minSteps(mice, holes) {    mice.sort((a, b) => a - b);     holes.sort((a, b) => a - b); let maxSteps = 0;     for (let i = 0; i < mice.length; i++) {         let steps = Math.abs(mice[i] - holes[i]);         if (steps > maxSteps) {             maxStep...
Read more

Today I have solved problem in javascript

 You are given an array X of floating-point numbers x1, x2, ... xn. These can be rounded up or down to create a corresponding array Y of integers y1, y2, ... yn. Write an algorithm that finds an appropriate Y array with the following properties: The rounded sums of both arrays should be equal. The absolute pairwise difference between elements is minimized. In other words, |x1- y1| + |x2- y2| + ... + |xn- yn| should be as small as possible. For example, suppose your input is [1.3, 2.3, 4.4]. In this case you cannot do better than [1, 2, 5], which has an absolute difference of |1.3 - 1| + |2.3 - 2| + |4.4 - 5| = 1. const inputArray = [1.3, 2.3, 4.4]; const resultArray = roundArray(inputArray); function roundArray(inputArray) {     const n = inputArray.length;     const roundedArray = [];     let roundedSum = 0; for (let i = 0; i < n; i++) {         consat roundedValue = Math.round(inputArray[i]);         rounded...
Read more