Blog

I recently discovered an intriguing technique that could be a game-changer for those of us who frequently deal with audits and accounting challenges at work, or those of us whom are practicing data structures and algorithms in our spare time. My favorite data types are dictionaries, also known as objects, because they allow us to associate multiple values with keys and access them in O(1) time. This efficiency has been invaluable in solving problems quickly.

The Challenge of Imprecise Key Access

One challenge I’ve encountered is finding easy explanations or notable methods for accessing a key imprecisely or through logic. I want keys to act as buckets that capture multiple values quickly. For instance, consider the cost of towing a 2125-pound vehicle, where the cost is hidden behind a interval based key like {(2000,2500): 245}. You can’t directly access this interval with 2125 because it doesn’t precisely match the key. Typically, you’d loop through the keys and use conditional checks, but that’s not efficient, and there’s limited literature on this specific use case.

Real-World Applications

Many accounting systems involve incremental charts of rates based on input quantities, such as charges based on weight, volume, or item quantity. As a simple, starter example, a fruit stand might offer discounts based on the number of bananas purchased. A simple formula might look like this:

function calculatePrice(quantity) {
  if (quantity <= 0) {
    return "Invalid quantity. Please enter a positive number.";
  }
  let price;
  if (quantity < 100) {
    price = 6;
  } else if (quantity < 200) {
    price = 5;
  } else if (quantity < 300) {
    price = 4;
  } else if (quantity < 400) {
    price = 3;
  } else if (quantity < 500) {
    price = 2;
  } else {
    price = 1;
  }
  const totalCost = quantity * price;
  return `For ${quantity} items, the price is $${price} each. Total cost: $${totalCost}`;
}

While hardcoding intervals into an if-else statement allows fast logical access to the rates, it’s not scalable or adaptable for other use cases. We need the flexibility to input a quantity and a dictionary of intervals into our function to find the rate. This way we can use on function on any sort of rate finding problem.

A More Flexible Approach

We can also use a dictionary or list matrix with thresholds and values. However, we lose the instant O(1) calculation because we can’t directly identify the relevant key in the dictionary. Here’s a more flexible approach:

const priceBreaks = {
  100: 6,
  200: 5,
  300: 4,
  400: 3,
  500: 2,
  Infinity: 1,
};

function calculatePrice(quantity) {
  if (quantity <= 0) {
    return "Invalid quantity. Please enter a positive number.";
  }
  let price;
  for (const [breakpoint, breakPrice] of Object.entries(priceBreaks)) {
    if (quantity < parseInt(breakpoint)) {
      price = breakPrice;
      break;
    }
  }
  const totalCost = quantity * price;
  return `For ${quantity} items, the price is $${price} each. Total cost: $${totalCost}`;
}

Achieving O(1) Time Complexity

In programming, we often check thousands of records against these charts. The simplest way is to use quantities as keys and rates as values. However, incremental charts indicate thresholds, not precise quantities. To find the correct bucket or threshold and the appropriate rate, we typically check each key incrementally, resulting in O(n) time complexity. How can we create a modular rate-finding function while maintaining O(1) time complexity?We can achieve this by applying Math.floor to the quantity divided by the increment, multiplying it by the increment, and then using Math.min with the max price break and the quantity previously calculated. This mathematical approach allows us to access the desired key’s rate value in O(1) time.

const priceBreaks = {
  0: 6,
  500: 5,
  600: 4,
  700: 3,
  800: 2,
  900: 1,
  min: 500,
  max: 900,
  increment: 100,
};

function calculatePrice(quantity) {
  if (quantity <= 0) {
    return "Invalid quantity. Please enter a positive number.";
  }

  // Calculate the price bracket
  let bracket = Math.min(
    Math.floor(quantity / priceBreaks["increment"]) * priceBreaks["increment"],
    priceBreaks["max"]
  );

  if (bracket < priceBreaks["min"]) bracket = 0;
  const price = priceBreaks[bracket];

  const totalCost = quantity * price;
  return `For ${quantity} items, the price is $${price} each. Total cost: $${totalCost}`;
} 

Conclusion

This method is particularly useful for large datasets with consistent intervals. By adding a minimum, maximum, and increment to your object, you can modify existing rates to fit this function without the need for looping through an object or dictionary. It’s a nifty solution for efficiently calculating rates across numerous records. This can be applied to big data sets with many interval breaks and calculate rates a quickly as possible