You are given an integer n, denoting the number of people who needs to be seated, and a list of m integers seats, where 0 represents a vacant seat and 1 represents an already occupied seat.
Find whether all n people can find a seat, provided that no two people can sit next to each other.
Example 1:
Input:
n = 2
m = 7
seats[] = {0, 0, 1, 0, 0, 0, 1}
Output:
Yes
Explanation:
The two people can sit at index 0 and 4.
Example 2:
Input:
n = 1
m = 3
seats[] = {0, 1, 0}
Output:
No
Explanation:
There is no way to get a seat for one person.
Your Task:
You don't have to input or print anything. Complete the function is_possible_to_get_seats() which takes the input parameters and return a boolean value, indicating whether all people can find a seat.
Expected Time Complexity: O(m)
Expected Space Complexity: O(1)
Constraints:
	0 <= n <= 10^{5}
	1 <= m <= 10^{5}
	seats[i] == 0 or seats[i] == 1

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Greedy algorithms

Starter code: 



from typing import List

class Solution:

    def is_possible_to_get_seats(self, n : int, m : int, seats : List[int]) -> bool:

        # code here

        



Solutions:
from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, arr: List[int]) -> bool:
		for i in range(0, m):
			if i == m - 1:
				if arr[i] == 0 and arr[i - 1] == 0:
					n = n - 1
					arr[i] = 1
			elif i == 0:
				if arr[0] == 0 and arr[1] == 0:
					n = n - 1
					arr[0] = 1
			elif arr[i] == 0 and arr[i - 1] == 0 and (arr[i + 1] == 0):
				n = n - 1
				arr[i] = 1
		if n <= 0:
			return True
		return False


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		if n == 0:
			return True
		elif n == m and n > 1:
			return False
		elif n == 1 and m == 1 and (seats[0] == 0):
			return True
		count = 0
		if seats[0] == 0 and seats[1] == 0:
			count += 1
			if count == n:
				return True
			for a in range(2, m - 1):
				if seats[a] == 0 and seats[a - 1] == 0 and (seats[a + 1] == 0):
					count += 1
					seats[a] = 1
					if count == n:
						return True
			if seats[m - 1] == 0 and seats[m - 2] == 0:
				count += 1
			if count == n:
				return True
			else:
				return False
		else:
			for a in range(2, m - 1):
				if seats[a] == 0 and seats[a - 1] == 0 and (seats[a + 1] == 0):
					count += 1
					if count == n:
						return True
			if seats[m - 1] == 0 and seats[m - 2] == 0:
				count += 1
			if count == n:
				return True
			else:
				return False


import math
from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		lastz = -1
		count = 0
		if m == 1 and seats[0] == 0:
			count = 1
		else:
			for i in range(m):
				if i == 0 and i + 1 < m and (seats[i] == 0) and (seats[i + 1] == 0):
					count += 1
					lastz = i
				if i != 0 and i < m - 1 and (seats[i] == 0) and (seats[i - 1] == 0) and (seats[i + 1] == 0):
					if i - 1 != lastz:
						count += 1
						lastz = i
				if i == m - 1 and i - 1 != lastz and (seats[i] == 0) and (seats[i - 1] == 0):
					count += 1
		if count >= n:
			return True
		else:
			return False


import math
from typing import List

class Solution:

	def calculateplaces(self, arr, start, i):
		x = i - start
		if start > 0:
			x = x - 1
		if i <= len(arr) - 1:
			x = x - 1
		return math.floor((x + 1) / 2)

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		start = -1
		count = 0
		if m == 1 and seats[0] == 0:
			count = 1
		for i in range(m):
			if start == -1 and seats[i] == 0:
				start = i
			elif start != -1 and seats[i] == 1:
				count += self.calculateplaces(seats, start, i)
				start = -1
			elif start != -1 and i == m - 1 and (seats[i] == 0):
				count += self.calculateplaces(seats, start, i + 1)
		if count >= n:
			return True
		else:
			return False


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		if n == 0:
			return True
		if m == 1:
			return seats[0] == 0
		if seats[0] == 0 and seats[1] == 0:
			seats[0] = 1
			n -= 1
		if seats[-1] == 0 and seats[-2] == 0:
			seats[-1] = 1
			n -= 1
		for i in range(1, m - 1):
			if seats[i - 1] == 0 and seats[i] == 0 and (seats[i + 1] == 0):
				seats[i] = 1
				n -= 1
		return n <= 0


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		available_seats = 0
		i = 0
		while i < m:
			prev = 0
			if i == 0:
				prev = 0
			else:
				prev = seats[i - 1]
			nxt = 0
			if i == m - 1:
				nxt = 0
			else:
				nxt = seats[i + 1]
			if prev + nxt + seats[i] == 0:
				available_seats += 1
				i += 1
			i += 1
		return available_seats >= n


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		if n > m:
			return False
		if n == 0:
			return True
		if m == 1:
			return seats[0] == 0
		i = 0
		while i < m:
			if seats[i] == 0:
				if i == 0:
					if seats[i + 1] != 1:
						n -= 1
						if n == 0:
							return True
						seats[i] = 1
				elif i == m - 1:
					if seats[i - 1] != 1:
						n -= 1
						if n == 0:
							return True
						seats[i] = 1
				elif seats[i - 1] != 1 and seats[i + 1] != 1:
					n -= 1
					if n == 0:
						return True
					seats[i] = 1
			i += 1
		return n == 0


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		count = 0
		for i in range(m):
			left = False
			right = False
			if i == 0 or seats[i - 1] == 0:
				left = True
			if i == m - 1 or seats[i + 1] == 0:
				right = True
			if seats[i] == 0 and left and right:
				seats[i] = 1
				count += 1
		return count >= n


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		if len(seats) > 1:
			for i in range(0, m - 1):
				if seats[0] == 0 and seats[1] == 0:
					n = n - 1
					seats[0] = 1
				elif seats[i - 1] == 0 and seats[i + 1] == 0 and (seats[i] == 0):
					n = n - 1
					seats[i] = 1
				elif i == m - 2 and seats[i] == 0 and (seats[i + 1] == 0):
					n = n - 1
					seats[i + 1] = 1
			if n <= 0:
				return 'Yes'
		else:
			if seats[0] == 0:
				n = n - 1
			if n <= 0:
				return 'Yes'


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		blank = 0
		for i in range(len(seats)):
			if blank == n:
				return True
			if seats[i] == 1:
				continue
			if i != 0:
				if seats[i - 1] == 1:
					continue
			if i != len(seats) - 1:
				if seats[i + 1] == 1:
					continue
			blank += 1
			seats[i] = 1
		if blank == n:
			return True
		return False


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		zero_count = 0
		seat_count = 0
		is_zero = False
		i = 0
		for s in seats:
			if s == 0:
				zero_count += 1
			else:
				zero_count -= 1
				seat_count += max((zero_count + 1) // 2, 0)
				zero_count = -1
		if zero_count > 0:
			seat_count += (zero_count + 1) // 2
		return seat_count >= n


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		i = 0
		while i < m:
			if seats[i] == 0 and n > 0:
				if (i == 0 or seats[i - 1] == 0) and (i == m - 1 or seats[i + 1] == 0):
					seats[i] = 1
					n -= 1
					i += 1
			i += 1
		return n == 0


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		capacity = 0
		i = 0
		while i < m:
			left = 0 if i == 0 else seats[i - 1]
			right = 0 if i == m - 1 else seats[i + 1]
			if seats[i] == 0 and left + right == 0:
				capacity += 1
				i += 2
			else:
				i += 1
		return capacity >= n


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, s: List[int]) -> bool:
		c = 0
		i = 0
		if n == 0:
			return 1
		elif len(s) == 1:
			return not s[0]
		while i < len(s):
			if i != 0 and i != len(s) - 1:
				if s[i] == 0 and s[i - 1] == 0 and (s[i + 1] == 0):
					c += 1
					i += 1
			elif i == 0:
				if s[i] == 0 and s[i + 1] == 0:
					c += 1
					i += 1
			elif i == len(s) - 1:
				if s[i] == 0 and s[i - 1] == 0:
					c += 1
					i += 1
			i += 1
		if c >= n:
			return 1
		else:
			return 0


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> int:
		c = 0
		if seats[0] == 0 and m == 1:
			return True
		for i in range(m - 1):
			if i != 0 and seats[i] == 0 and (seats[i - 1] == 0) and (seats[i + 1] == 0):
				c += 1
				seats[i] = 1
			elif i == 0 and seats[i] == 0 and (seats[i + 1] == 0):
				c += 1
				seats[i] = 1
		if seats[m - 1] == 0 and seats[m - 2] == 0:
			c += 1
		if c >= n:
			return True
		else:
			return False


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		c = 0
		if n > m:
			return 0
		seats.insert(0, 0)
		seats.append(0)
		i = 1
		while i < m + 1:
			if seats[i - 1] == 0 and seats[i] == 0 and (seats[i + 1] == 0):
				c += 1
				i += 2
			else:
				i += 1
		if c >= n:
			return 1
		else:
			return 0


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		(cnt, ans) = (1, 0)
		for e in seats:
			if e == 0:
				cnt += 1
			else:
				ans += max(0, (cnt - 1) // 2)
				cnt = 0
		cnt += 1
		return ans + (cnt - 1) // 2 >= n


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		seat = 0
		while seat < m and n:
			if seat + 1 < m and seats[seat + 1] == 1:
				seat += 3
				continue
			if seats[seat] == 1:
				seat += 2
				continue
			if seat > 0 and seats[seat - 1] == 1:
				seat += 1
				continue
			n -= 1
			seat += 2
		return n == 0


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		vacant_seats = 0
		if m == 1 and n == 1:
			if seats[m - 1] == 0:
				return True
			else:
				return False
		elif m == 2 and n == 1:
			if seats[0] or seats[1] == 1:
				return False
			else:
				return True
		else:
			for x in range(m):
				if x == 0:
					if seats[x] == 0 and seats[x + 1] == 0:
						seats[x] = 1
						vacant_seats += 1
				elif x == m - 1:
					if seats[x] == 0 and seats[x - 1] == 0:
						seats[x] = 1
						vacant_seats += 1
				elif seats[x] == 0:
					if seats[x + 1] == 0 and seats[x - 1] == 0:
						seats[x] = 1
						vacant_seats += 1
		if vacant_seats < n:
			return False
		else:
			return True


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		if n == 1 and seats == [0]:
			return True
		current_seq = 0
		available_slots = []
		flag = False
		for idx in range(len(seats)):
			if idx == 0 and seats[idx] == 0:
				flag = True
			if idx == len(seats) - 1 and seats[idx] == 0:
				flag = True
			if seats[idx] == 0:
				current_seq += 1
			else:
				if current_seq > 0:
					available_slots.append((current_seq, flag))
				current_seq = 0
				flag = False
		if current_seq != 0:
			available_slots.append((current_seq, flag))
		idx = 0
		while idx < len(available_slots) and n > 0:
			if available_slots[idx][1]:
				can_sit = available_slots[idx][0] // 2
			else:
				can_sit = (available_slots[idx][0] - 1) // 2
			idx += 1
			n -= can_sit
		if n <= 0:
			return True
		return False


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		for i in range(m):
			if seats[i] == 0:
				front_empty = False
				next_empty = False
				if i - 1 < 0 or seats[i - 1] == 0:
					front_empty = True
				if i + 1 >= m or seats[i + 1] == 0:
					next_empty = True
				if front_empty and next_empty:
					n -= 1
					seats[i] = 1
		if n <= 0:
			return True
		return False


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		nmax = 0
		skipNext = False
		for k in range(m):
			if skipNext:
				skipNext = False
				continue
			if k > 0:
				if seats[k - 1] == 1:
					continue
			if k < m - 1:
				if seats[k + 1] == 1:
					continue
			if seats[k] == 1:
				continue
			nmax += 1
			skipNext = True
		return nmax >= n


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		if len(seats) == 1:
			if seats[0] == 0:
				return n <= 1
			if seats[0] == 1:
				return n == 0
		possible_seats = 0
		for i in range(len(seats)):
			if possible_seats == n:
				break
			if seats[i] == 0:
				if i == 0:
					if seats[i + 1] == 0:
						seats[i] = 1
						possible_seats += 1
				elif i == len(seats) - 1:
					if seats[i - 1] == 0:
						seats[i] = 1
						possible_seats += 1
				elif seats[i - 1] == 0 and seats[i + 1] == 0:
					seats[i] = 1
					possible_seats += 1
		return possible_seats == n


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		if n == 0:
			return True
		count = 0
		(l, r) = (-1, 0)
		for r in range(m):
			if seats[r] == 1:
				if l == -1:
					count += r // 2
				elif r - l != 1:
					count += (r - l - 1) // 2
					count -= 1 if (r - l - 1) % 2 == 0 else 0
				l = r
		if l == -1:
			return m // 2 + m % 2 >= n
		if seats[-1] == 0:
			count += (m - l - 1) // 2
		return count >= n


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		count = 0
		seats.insert(0, 0)
		seats.append(0)
		for i in range(1, m + 1):
			if not any(seats[i - 1:i + 2]):
				seats[i] = 1
				count += 1
		return count >= n


from typing import List

class Solution:

	def is_possible_to_get_seats(self, n: int, m: int, seats: List[int]) -> bool:
		arr = seats[:]
		c = 0
		if len(arr) > 2:
			arr.append(0)
			for i in range(len(arr) - 1):
				if arr[i] == 0 and arr[i - 1] == 0 and (arr[i + 1] == 0):
					c = c + 1
					arr[i] = 1
			if c >= n:
				return 1
			return 0
		else:
			if len(arr) == 1 and arr[0] == 0 and (n == 1):
				return 1
			for i in range(len(arr) - 1):
				if arr[i] == 0 and arr[i + 1] == 0:
					c = c + 1
			if c >= n:
				return 1
			return 0