Find a seat with Distance between nearest Occupied Seats maximised
Given a string (seats) of 1s and 0s, where 1 represents a filled seat and 0 represents an empty seat in a row. Find an empty seat with maximum distance from an occupied seat. Return the maximum distance.
Examples:
Input: Seats = “1000101”
Output: 2
Explanation: Geek can take 3rd place and have a distance of 2 in left and 2 in right.Input: Seats = “1000”
Output: 3
Explanation: Geek can take the rightmost seat to have a distance of 3.
Approach:
The approach involves traversing the string while maintaining a count of consecutive empty seats. Whenever an occupied seat (‘1’) is encountered, the algorithm computes the distance and adjusts the maximum distance if required. In addition to considering the empty seats in the middle, it’s essential to account for both the initial and final empty seats to determine the maximum distance accurately.
Below is the implementation of the above approach.
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
using namespace std;
int maxDistToClosest(string seats)
{
// Initialize the maximum distance to -1
int max_distance = -1;
// Initialize a variable to count consecutive empty
// seats
int consecutiveEmptySeats = 0;
// Iterate through the binary string 'seats'
for (int i = 0; i < seats.length(); ++i) {
if (seats[i] == '0') {
// Increment the count for consecutive empty
// seats
consecutiveEmptySeats++;
}
else if (seats[i] == '1' && max_distance == -1) {
// Update 'max_distance' with
// 'consecutiveEmptySeats' if it's the first
// occupied seat
max_distance = consecutiveEmptySeats;
// Reset the count of consecutive empty seats
consecutiveEmptySeats = 0;
}
else {
// Update 'max_distance' with half of
// 'consecutiveEmptySeats' if not the first
// occupied seat
max_distance
= max(max_distance,
static_cast<int>(ceil(
consecutiveEmptySeats / 2.0)));
// Reset the count of consecutive empty seats
consecutiveEmptySeats = 0;
}
}
// Update 'max_distance' one more time after the loop
// for any consecutive empty seats at the end
max_distance = max(max_distance, consecutiveEmptySeats);
return max_distance;
}
// Driver Code
int main()
{
string seats = "1000101";
// Calling and printing the result
cout << maxDistToClosest(seats) << endl;
return 0;
}
// Java implementation:
public class Main {
public static int maxDistToClosest(String seats) {
// Initialize the maximum distance to -1
int max_distance = -1;
// Initialize a variable to count consecutive empty seats
int consecutiveEmptySeats = 0;
// Iterate through the binary string 'seats'
for (int i = 0; i < seats.length(); ++i) {
if (seats.charAt(i) == '0') {
// Increment the count for consecutive empty seats
consecutiveEmptySeats++;
} else if (seats.charAt(i) == '1' && max_distance == -1) {
// Update 'max_distance' with 'consecutiveEmptySeats' if it's the first occupied seat
max_distance = consecutiveEmptySeats;
// Reset the count of consecutive empty seats
consecutiveEmptySeats = 0;
} else {
// Update 'max_distance' with half of 'consecutiveEmptySeats' if not the first occupied seat
max_distance = Math.max(max_distance, (int) Math.ceil(consecutiveEmptySeats / 2.0));
// Reset the count of consecutive empty seats
consecutiveEmptySeats = 0;
}
}
// Update 'max_distance' one more time after the loop for any consecutive empty seats at the end
max_distance = Math.max(max_distance, consecutiveEmptySeats);
return max_distance;
}
public static void main(String[] args) {
String seats = "1000101";
// Calling and printing the result
System.out.println(maxDistToClosest(seats));
}
}
// This code is contributed by Sakshi
import math
def maxDistToClosest(seats):
# Initialize the maximum distance to -1
max_distance = -1
# Initialize a variable to count consecutive empty seats
ConsecutiveEmptySeats = 0
# Iterate through the binary string 'seats'
for i in range(len(seats)):
if seats[i] == '0':
# Increment the count for consecutive empty seats
ConsecutiveEmptySeats += 1
elif seats[i] == '1' and max_distance == -1:
# Update 'max_distance' with 'ConsecutiveEmptySeats' if it's the first occupied seat
max_distance = ConsecutiveEmptySeats
# Reset the count of consecutive empty seats
ConsecutiveEmptySeats = 0
else:
# Update 'max_distance' with half of 'ConsecutiveEmptySeats' if not the first occupied seat
max_distance = max(max_distance, math.ceil(ConsecutiveEmptySeats / 2))
# Reset the count of consecutive empty seats
ConsecutiveEmptySeats = 0
# Update 'max_distance' one more time after the loop
# for any consecutive empty seats at the end
max_distance = max(max_distance, ConsecutiveEmptySeats)
return max_distance
# Driver code
seats = '1000101'
# Calling and printing the result
print(maxDistToClosest(seats))
using System;
public class GFG
{
public static int MaxDistToClosest(string seats)
{
// Initialize the maximum distance to -1
int maxDistance = -1;
// Initialize a variable to count consecutive empty seats
int consecutiveEmptySeats = 0;
// Iterate through the binary string 'seats'
for (int i = 0; i < seats.Length; ++i)
{
if (seats[i] == '0')
{
// Increment the count for consecutive empty seats
consecutiveEmptySeats++;
}
else if (seats[i] == '1' && maxDistance == -1)
{
// Update 'maxDistance' with 'consecutiveEmptySeats' if it's the first occupied seat
maxDistance = consecutiveEmptySeats;
// Reset the count of consecutive empty seats
consecutiveEmptySeats = 0;
}
else
{
// Update 'maxDistance' with half of
// 'consecutiveEmptySeats' if not the first occupied seat
maxDistance = Math.Max(maxDistance,
(int)Math.Ceiling(consecutiveEmptySeats / 2.0));
// Reset the count of consecutive empty seats
consecutiveEmptySeats = 0;
}
}
// Update 'maxDistance' one more time after the loop for any
// consecutive empty seats at the end
maxDistance = Math.Max(maxDistance, consecutiveEmptySeats);
return maxDistance;
}
public static void Main(string[] args)
{
string seats = "1000101";
// Calling and printing the result
Console.WriteLine(MaxDistToClosest(seats));
}
}
function maxDistToClosest(seats) {
// Initialize the maximum distance to -1
let maxDistance = -1;
// Initialize a variable to count
// consecutive empty seats
let consecutiveEmptySeats = 0;
// Iterate through the string 'seats'
for (let i = 0; i < seats.length; ++i) {
if (seats[i] === '0') {
// Increment the count for consecutive
// empty seats
consecutiveEmptySeats++;
}
else if (seats[i] === '1' && maxDistance === -1) {
// Update 'maxDistance' with 'consecutiveEmptySeats'
// if it's the first occupied seat
maxDistance = consecutiveEmptySeats;
// Reset the count of consecutive empty seats
consecutiveEmptySeats = 0;
}
else {
// Update 'maxDistance' with half of
// 'consecutiveEmptySeats' if not the
// first occupied seat
maxDistance = Math.max(
maxDistance,
Math.ceil(consecutiveEmptySeats / 2)
);
// Reset the count of consecutive empty seats
consecutiveEmptySeats = 0;
}
}
// Update 'maxDistance' one more time after the
// loop for any consecutive empty seats at the end
maxDistance = Math.max(maxDistance, consecutiveEmptySeats);
return maxDistance;
}
// Driver Code
const seats = "1000101";
// Calling and printing the result
console.log(maxDistToClosest(seats));
Output
2
Time Complexity: O(N), where n is the number of seats.
Auxiliary Space: O(1).
Approach 2: Using Preprocessing
This approach involves preprocessing the string to the identify the distance of the each empty seat from the nearest occupied seat. We iterate through the string once to the compute this distance for the each empty seat. Then, we return the maximum distance among all empty seats.
Below is the implementation of the above approach.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int GFG(string seats)
{
int n = seats.length();
vector<int> distanceToLeft(n, n), distanceToRight(n, n);
int nearestOccupied = -n;
// Preprocess distance to left
for (int i = 0; i < n; ++i) {
if (seats[i] == '1') {
nearestOccupied = i;
}
else {
distanceToLeft[i] = i - nearestOccupied;
}
}
// Reset nearestOccupied for next iteration
nearestOccupied = 2 * n;
// Preprocess distance to right
for (int i = n - 1; i >= 0; --i) {
if (seats[i] == '1') {
nearestOccupied = i;
}
else {
distanceToRight[i] = nearestOccupied - i;
}
}
// Calculate maximum distance
int maxDistance = 0;
for (int i = 0; i < n; ++i) {
if (seats[i] == '0') {
maxDistance
= max(maxDistance, min(distanceToLeft[i],
distanceToRight[i]));
}
}
return maxDistance;
}
int main()
{
string seats = "1000101";
cout << GFG(seats) << endl;
return 0;
}
public class GFG {
public static int maxDistance(String seats)
{
int n = seats.length();
int[] distanceToLeft = new int[n];
int[] distanceToRight = new int[n];
int nearestOccupied = -n;
// Preprocess distance to left
for (int i = 0; i < n; i++) {
if (seats.charAt(i) == '1') {
nearestOccupied = i;
}
else {
distanceToLeft[i] = i - nearestOccupied;
}
}
// Reset nearestOccupied for next iteration
nearestOccupied = 2 * n;
// Preprocess distance to right
for (int i = n - 1; i >= 0; i--) {
if (seats.charAt(i) == '1') {
nearestOccupied = i;
}
else {
distanceToRight[i] = nearestOccupied - i;
}
}
// Calculate maximum distance
int maxDistance = 0;
for (int i = 0; i < n; i++) {
if (seats.charAt(i) == '0') {
maxDistance = Math.max(
maxDistance,
Math.min(distanceToLeft[i],
distanceToRight[i]));
}
}
return maxDistance;
}
// Test the function
public static void main(String[] args)
{
String seats = "1000101";
System.out.println(maxDistance(seats));
}
}
def GFG(seats):
n = len(seats)
distanceToLeft = [n]*n
distanceToRight = [n]*n
nearestOccupied = -n
# Preprocess distance to left
for i in range(n):
if seats[i] == '1':
nearestOccupied = i
else:
distanceToLeft[i] = i - nearestOccupied
# Reset nearestOccupied for next iteration
nearestOccupied = 2 * n
# Preprocess distance to right
for i in range(n-1, -1, -1):
if seats[i] == '1':
nearestOccupied = i
else:
distanceToRight[i] = nearestOccupied - i
# Calculate maximum distance
maxDistance = 0
for i in range(n):
if seats[i] == '0':
maxDistance = max(maxDistance, min(
distanceToLeft[i], distanceToRight[i]))
return maxDistance
# Test the function
seats = "1000101"
print(GFG(seats))
function maxDistance(seats) {
const n = seats.length;
const distanceToLeft = new Array(n).fill(0);
const distanceToRight = new Array(n).fill(0);
let nearestOccupied = -n;
// Preprocess distance to left
for (let i = 0; i < n; i++) {
if (seats.charAt(i) === '1') {
nearestOccupied = i;
} else {
distanceToLeft[i] = i - nearestOccupied;
}
}
// Reset nearestOccupied for next iteration
nearestOccupied = 2 * n;
// Preprocess distance to right
for (let i = n - 1; i >= 0; i--) {
if (seats.charAt(i) === '1') {
nearestOccupied = i;
} else {
distanceToRight[i] = nearestOccupied - i;
}
}
// Calculate maximum distance
let maxDistance = 0;
for (let i = 0; i < n; i++) {
if (seats.charAt(i) === '0') {
maxDistance = Math.max(
maxDistance,
Math.min(distanceToLeft[i], distanceToRight[i])
);
}
}
return maxDistance;
}
// Test the function
const seats = "1000101";
console.log(maxDistance(seats));
Output
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us