683. K Empty Slots

LeetCode hard original: C# #array #csharp #hard #hash-table #leetcode #sort

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

У вас есть n лампочек, расположенных в ряд и пронумерованных от 1 до n. Изначально все лампочки выключены. Каждый день мы включаем ровно одну лампочку, и через n дней все лампочки будут включены.

Вам дан array bulbs длины n, где bulbs[i] = x означает, что в (i+1)-й день мы включим лампочку в позиции x, где i индексируется с 0, а x индексируется с 1.

given integer k, return minimum номер дня, такой что существует две включенные лампочки, между которыми ровно k выключенных лампочек. Если такого дня не существует, return -1.

Example:

Input: bulbs = [1,3,2], k = 1

Output: 2

Explanation:

On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]

On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]

On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]

We return 2 because on the second day, there were two on bulbs with one off bulb between them.

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int KEmptySlots(int[] bulbs, int k) {
        SortedSet<int> active = new SortedSet<int>();
        int day = 0;
        
        foreach (int bulb in bulbs) {
            day++;
            active.Add(bulb);
            var lower = active.GetViewBetween(0, bulb - 1).Max;
            var higher = active.GetViewBetween(bulb + 1, int.MaxValue).Min;
            
            if ((lower != null && bulb - lower - 1 == k) ||
                (higher != null && higher - bulb - 1 == k)) {
                return day;
            }
        }
        return -1;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int KEmptySlots(vector<int>& bulbs, int k) {
        SortedSet<int> active = new SortedSet<int>();
        int day = 0;
        
        foreach (int bulb in bulbs) {
            day++;
            active.push_back(bulb);
            var lower = active.GetViewBetween(0, bulb - 1).Max;
            var higher = active.GetViewBetween(bulb + 1, int.MaxValue).Min;
            
            if ((lower != null && bulb - lower - 1 == k) ||
                (higher != null && higher - bulb - 1 == k)) {
                return day;
            }
        }
        return -1;
    }
}

Java solution

matched/original

import java.util.TreeSet;

class Solution {
    public int kEmptySlots(int[] flowers, int k) {
        TreeSet<Integer> active = new TreeSet<>();
        int day = 0;
        
        for (int flower : flowers) {
            day++;
            active.add(flower);
            Integer lower = active.lower(flower);
            Integer higher = active.higher(flower);
            
            if ((lower != null && flower - lower - 1 == k) ||
                (higher != null && higher - flower - 1 == k)) {
                return day;
            }
        }
        return -1;
    }
}

JavaScript solution

matched/original

class Solution {
    kEmptySlots(bulbs, k) {
        const active = new Set();
        let day = 0;
        
        for (const bulb of bulbs) {
            day++;
            active.add(bulb);
            const lower = Array.from(active).filter(b => b < bulb).sort((a, b) => b - a)[0];
            const higher = Array.from(active).filter(b => b > bulb).sort((a, b) => a - b)[0];
            
            if ((lower !== undefined && bulb - lower - 1 == k) ||
                (higher !== undefined && higher - bulb - 1 == k)) {
                return day;
            }
        }
        return -1;
    }
}

Python solution

matched/original

from sortedcontainers import SortedList

class Solution:
    def kEmptySlots(self, flowers: List[int], k: int) -> int:
        active = SortedList()
        day = 0
        
        for flower in flowers:
            day += 1
            active.add(flower)
            idx = active.index(flower)
            
            if idx > 0 and flower - active[idx - 1] - 1 == k:
                return day
            if idx < len(active) - 1 and active[idx + 1] - flower - 1 == k:
                return day
        
        return -1

Go solution

matched/original

package main

import "container/list"

func kEmptySlots(flowers []int, k int) int {
    active := list.New()
    day := 0
    
    for _, flower := range flowers {
        day++
        e := active.PushBack(flower)
        prev := e.Prev()
        next := e.Next()
        
        if prev != nil && flower - prev.Value.(int) - 1 == k {
            return day
        }
        if next != nil && next.Value.(int) - flower - 1 == k {
            return day
        }
        
        for p := active.Front(); p != nil; p = p.Next() {
            if p.Value.(int) > flower {
                active.MoveBefore(e, p)
                break
            }
        }
    }
    return -1
}

Algorithm

Поддерживайте active, отсортированную структуру данных, содержащую каждую лампочку, которая в данный момент включена. Это позволит быстро находить соседей для вновь добавленных лампочек и проверять условия задачи.

Когда вы добавляете лампочку в active, проверьте ее нижних и верхних соседей. Для этого find ближайшие включенные лампочки с обеих сторон и проверьте количество выключенных лампочек между ними.

Если какой-то сосед удовлетворяет условию (ровно k выключенных лампочек между двумя включенными), значит, Statement впервые произошло в этот день, и вы можете вернуть номер этого дня. Если такого дня не существует после включения всех лампочек, return -1.

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.