3454.js

/** ------------------------------------------------------------------------------
 * 
 * 3454. Separate Squares II
 * Topics: Array, Binary Search
 * https://leetcode.com/problems/separate-squares-ii/description/?envType=daily-question&envId=2026-01-14
 * 
 ------------------------------------------------------------------------------ */
const separateSquares = (squares) => {
  if (!squares || squares.length === 0) return 0

  const sampleY = squares[0][1]
  const sampleL = squares[0][2]
  let allSameYAndL = true
  for (let i = 1; i < squares.length; i++) {
    if (squares[i][1] !== sampleY || squares[i][2] !== sampleL) {
      allSameYAndL = false
      break
    }
  }
  if (allSameYAndL) return sampleY + sampleL / 2

  const events = []
  const xSet = new Set()
  for (const [x, y, l] of squares) {
    const x2 = x + l
    events.push([y, 0, x, x2])
    events.push([y + l, 1, x, x2])
    xSet.add(x)
    xSet.add(x2)
  }

  events.sort((a, b) => {
    if (a[0] !== b[0]) return a[0] - b[0]
    return a[1] - b[1]
  })

  const sortedX = [...xSet].sort((a, b) => a - b)
  const xToIndex = new Map()
  for (let i = 0; i < sortedX.length; i++) {
    xToIndex.set(sortedX[i], i)
  }

  const n = sortedX.length
  const intervals = new Array(n - 1).fill(0)
  const widths = new Array(n - 1)
  for (let i = 0; i < n - 1; i++) {
    widths[i] = sortedX[i + 1] - sortedX[i]
  }

  let totalArea = 0
  let prevY = events[0][0]
  let activeWidth = 0
  for (let i = 0; i < events.length; i++) {
    const event = events[i]
    const y = event[0]
    const type = event[1]
    const x1 = event[2]
    const x2 = event[3]

    if (y > prevY) {
      totalArea += activeWidth * (y - prevY)
    }

    const leftIndex = xToIndex.get(x1)
    const rightIndex = xToIndex.get(x2)
    const delta = type === 0 ? 1 : -1
    for (let j = leftIndex; j < rightIndex; j++) {
      const wasActive = intervals[j] > 0
      intervals[j] += delta
      const isActive = intervals[j] > 0
      if (!wasActive && isActive) {
        activeWidth += widths[j]
      } else if (wasActive && !isActive) {
        activeWidth -= widths[j]
      }
    }

    prevY = y
  }

  intervals.fill(0)
  let currentArea = 0
  prevY = events[0][0]
  activeWidth = 0
  const halfTotalArea = totalArea / 2

  for (let i = 0; i < events.length; i++) {
    const event = events[i]
    const y = event[0]
    const type = event[1]
    const x1 = event[2]
    const x2 = event[3]

    if (y > prevY) {
      const segmentArea = activeWidth * (y - prevY)
      if (currentArea + segmentArea >= halfTotalArea) {
        if (activeWidth > 0) {
          const neededArea = halfTotalArea - currentArea
          return prevY + neededArea / activeWidth
        }
        return prevY
      }
      currentArea += segmentArea
    }

    const leftIndex = xToIndex.get(x1)
    const rightIndex = xToIndex.get(x2)
    const delta = type === 0 ? 1 : -1
    for (let j = leftIndex; j < rightIndex; j++) {
      const wasActive = intervals[j] > 0
      intervals[j] += delta
      const isActive = intervals[j] > 0
      if (!wasActive && isActive) {
        activeWidth += widths[j]
      } else if (wasActive && !isActive) {
        activeWidth -= widths[j]
      }
    }

    prevY = y
  }

  return events[events.length - 1][0]
}

console.log(
  separateSquares([
    [0, 0, 1],
    [2, 2, 1],
  ]),
)