CODEWITHSUNDEEP
javascriptalgorithmnumbers
oldboy
oldboy

Reputation: 5954

How to assign the lowest possible number which is not already assigned

What I am doing is dynamically creating elements and appending them to the page. The elements need to have an id, so I assign each of them a numerical id when the element is created. However, elements can and will be removed in a non-linear fashion, so you can end up having gaps between values like so...

One hypothetical scenario: 1, 3, 4, 5, 16, 22.

In the case above, if I were to create an element, I would want to assign 2 as its id.

Another hypothetical scenario: 3, 4, 5.

In this case, 1 should be assigned as the id.

I have written the code below, which should work fine, but I feel like it is unnecessarily complex. Does anybody have any idea how to improve upon it?!

const divs = element.getElementsByTagName('div')
for (let i = 0; i < divs.length; i++) {
  if (i > 0 && Number(divs[i].id) > Number(divs[i-1].id)+1 ) {
    return Number(divs[i-1].id)+1
    break
  } else if (i === divs.length-1) {
    return Number(divs[divs.length-1].id)+1
  } else if (Number(divs[0].id) > 1) {
    return 1
    break
  } else if (divs.length === 1 && Number(divs[0].id) === 1) {
    return 2
  } else if (divs.length === 1 && Number(divs[0].id) !== 1) {
    return 1
  }
}

I've chosen to take elsyr's advice and track the IDs. This will allow me to implement the following code, which is optimal given the circumstances.

const lowestNum = lowestId()
div.id = lowestNum
numericalIds[lowestNum-1] = lowestNum

function lowestId(){
  for (let i = 0; i < numericalIds.length; i++) {
    if (!numericalIds[i]) {
      return i+1
    } else if (i === numericalIds.length-1) {
      return numericalIds[numericalIds.length-1]+1
    }
  }
  return 1
}

I simply have to update the array right before elements are removed from the page.

numericalIds[/*numerical value of id*/-1] = 0 // or null or undefined

This will always create IDs with the smallest numerical value that is not already assigned and is no smaller than 1.

Upvotes: 3

Views: 118

Answers (4)

charlietfl
charlietfl

Reputation: 171669

Fairly straightforward approach that doesn't require fancy logic

const elems = document.querySelector('#container').children;

const getNextId = (els) => {
  let next = 1;
  if (elems) {// skip this if no existing elements
    const set = new Set([...els].map(({id}) => +id));
    while (set.has(next)) {
      next++;
    }
  }
  return next;
}

console.log('Next id: ', getNextId(elems))
<div id="container">
  <div id="2">2</div>
  <div id="1">1</div>
  <div id="3">3</div>
  <div id="4">4</div>
  <div id="5">5</div>
  <div id="16">16</div>
  <div id="22">22</div>
</div>

Upvotes: 1

Mamun
Mamun

Reputation: 68943

You can do the following:

let el = document.querySelectorAll('div:not(#container)');
let elArray = [...el].map(i=>i.getAttribute('id'));
var arrayLength = Math.max.apply(Math, elArray);
var missing = [];

for ( var i = 1; i <= arrayLength; i++ ) {
    if ( elArray.indexOf(i.toString()) < 0 ) {
        missing.push(i);
    }
}
missing = missing.map(item => parseInt(item));
var min = Math.min.apply(Math, missing);
console.log('Lowest possible id is: ', min);

// Create element
var div = document.createElement("DIV");
div.setAttribute('id', min);
var container = document.getElementById('container');
container.appendChild(div);
document.getElementById(min.toString()).innerHTML = min;
<div id="container">
  <div id="1">1</div>
  <div id="3">3</div>
  <div id="4">4</div>
  <div id="5">5</div>
  <div id="16">16</div>
</div>

Upvotes: 1

David Calhoun
David Calhoun

Reputation: 8581

This is a more functional approach, it should do what you need. It basically takes advantage of sparse arrays.

// Find all DOM elements with ids in the container.
const idElements = document.body.querySelectorAll('#container div[id]');

// Get all ids from the DOM elements.
// Note: first have to convert to a real array ([...idElements])
const allIds = [...idElements].map(domElement => parseInt(domElement.id));

// Filter out non-numbers.
const numericIds = allIds.filter(id => Number.isInteger(id));

// Creates a sparse array, e.g. [undefined, true, undefined].
// (The array index of undefined values are available id slots)
const arrayWithGaps = numericIds.reduce((accum, val) => {
  accum[val] = true;
  return accum;
}, []);

// Find the first empty index - this will be the lowest ID available.
const lowestAvailableId = arrayWithGaps.findIndex(val => typeof val === 'undefined');

console.log(lowestAvailableId);
<div id="container">
  <div id="0"></div>
  <div id="1"></div>
  <div id="3"></div>
  <div id="4"></div>
  <div id="5"></div>
  <div id="16"></div>
  <div id="22"></div>
</div>

EDIT: if reduce is a bit foreign or less readable, you could use forEach instead. Actually, maybe it makes more sense here anyway:

const arrayWithGaps = [];
numericIds.forEach(id => arrayWithGaps[id] = true);

Upvotes: 2

elsyr
elsyr

Reputation: 796

If we're talking about algorithmic complexity, your implementation is O(n) worst case. If you want to do better, you're probably going to need to employ a more appropriate data structure to store your IDs.

Something like a priority queue/min heap would be a little better, but you also said that your relatively simple loop is already too complex - you'd have to be willing to find a good library or write them up yourself and that's not necessarily more simple. I won't write up an implementation here, because I think that's out of the scope of a post like this.

Assuming we have this concept of 'free' IDs and 'taken' IDs, and we're calling insert when we 'free' up an ID, and pop when we 'take' an ID, using the above DS allows us to drop worst case complexity down to O(logn), as opposed to traversing the entire array. It would look something like this (omitting the actual minHeap implementation):

function takeLowestAvailableID() {
    return minHeap.pop();
}

function freeID(int freed) {
    minHeap.push(freed);
}

Note that these are worst case runtime complexities, and that we haven't even talked about memory considerations

It's difficult to make an end-all, be-all suggestion without knowing more about your application and how your data is coming into existence. If you are only storing IDs from 1-50 and 99% of the time, your application only ever uses 1-10, it might be worth just sticking with the function you have now.

Upvotes: 4

Related Questions