find index with maximum distance between two occupied seats |Amazon

Round 1

Questions: Find the index where a bit should be set such that the minimum distance to the nearest set bit (1) is maximized.

import java.util.*;

class MaximizeDistance {
    public static int maxDistSeatIndex(int[] seats) {
        int n = seats.length;
        int maxDistance = 0;
        int bestSeat = -1;
        int lastOccupied = -1;

        int[] rightOccupied = new int[n];

        // First pass: Fill rightOccupied array with nearest occupied seat to the right
        for (int i = n - 1; i >= 0; i--) {
            if (seats[i] == 1) {
                lastOccupied = i;
            }
            rightOccupied[i] = lastOccupied;
        }

        lastOccupied = -1;

        // Second pass: Find the best seat to flip to 1
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                lastOccupied = i;
            } else {
                // Distance from the nearest left and right occupied seat
                int leftDist = (lastOccupied == -1) ? Integer.MAX_VALUE : i - lastOccupied;
                int rightDist = (rightOccupied[i] == -1) ? Integer.MAX_VALUE : rightOccupied[i] - i;

                int minDist = Math.min(leftDist, rightDist); // Take the min of left and right distances

                if (minDist > maxDistance) {
                    maxDistance = minDist;
                    bestSeat = i;
                }
            }
        }

        return bestSeat; // Return the index to flip
    }

    public static void main(String[] args) {
        int[] seats = {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0}; //6
        int[] seats={1,0,0,0};//3
        int[] seats={0,0,0,1};//0
        System.out.println(maxDistSeatIndex(seats)); 
    }
}