Cracking The Coding Interview Together – Problem 5.8: Draw Line

Imagine you are writing a rendering engine for an ultra-low-power e-ink display or an embedded medical device. Memory is incredibly scarce, and every CPU cycle directly impacts battery life. In these environments, we do not have the luxury of modern high-level graphics libraries. Instead, we are dealing directly with a raw framebuffer: a single, contiguous array of bytes representing a monochrome screen.

If we need to draw a simple horizontal line, our first instinct might be to loop through every single pixel from start to finish, setting them one by one. But as senior engineers, we know that pixel-by-pixel manipulation is a performance bottleneck. It forces the CPU to perform redundant read-modify-write operations on the same byte of memory over and over again.

Our goal today is to design and implement an incredibly efficient, production-ready algorithm to draw a horizontal line. We will bypass the slow pixel-by-pixel approach and instead operate at the byte level, leveraging bitwise operations to write entire blocks of memory in a single instruction. Let's roll up our sleeves and master this low-level challenge together.

Problem Statement

The problem asks us to implement a function that draws a horizontal line on a monochrome screen. The screen is represented as a single-dimensional array of bytes (byte[] screen). Each byte contains 8 consecutive pixels, where a 1 represents a dark pixel (drawn) and a 0 represents a light pixel (empty).

The screen has a width W (in pixels), where W is guaranteed to be divisible by 8. The height of the screen can be inferred from the length of the array and the width. We need to implement the following method:

public static void drawLine(byte[] screen, int width, int x1, int x2, int y)

This method must draw a horizontal line from coordinate (x1, y) to (x2, y) (inclusive) by modifying the screen array in-place.

Analyze the Problem Together

To solve this efficiently, we must first understand how the 2D screen coordinates map to our 1D byte array. Since the screen width is W pixels, and there are 8 pixels per byte, each row of the screen occupies exactly W / 8 bytes. Let's call this value the byteWidth.

For any given coordinate (x, y), we can locate its corresponding byte and bit position using the following formulas:

• Byte Index: int byteIndex = (y * byteWidth) + (x / 8);
• Bit Offset: int bitOffset = x % 8;

The "Aha!" moment of this problem lies in recognizing that a horizontal line spans across three distinct regions of bytes:

1. The Start Byte: A partial byte where the line begins at x1. We only want to set the bits from x1 % 8 to the end of this byte.
2. The Middle Bytes: Zero or more fully aligned bytes that are completely covered by the line. We can set these entire bytes to 0xFF (all 1s) in a single write operation!
3. The End Byte: A partial byte where the line ends at x2. We only want to set the bits from the start of this byte up to x2 % 8.

Let's compare the naive approach against our optimized byte-aligned approach to see why this distinction is so critical:

By shifting our perspective from individual pixels to byte boundaries, we can dramatically reduce the number of memory writes, which is the most expensive operation in low-level rendering.

Questions for the Interviewer

Before we write a single line of code, a senior engineer always clarifies the boundaries and assumptions of the system. Here are the key questions we should ask our interviewer:

1. Bit Ordering (Endianness): "Is pixel 0 represented by the Most Significant Bit (MSB, 0x80) or the Least Significant Bit (LSB, 0x01) of the byte?"
   Assumption: We will assume MSB-to-LSB ordering. This means the leftmost pixel in a byte corresponds to the highest bit (index 0 is 10000000).
2. Coordinate Validation: "Can we assume that x1, x2, and y are always within the valid bounds of the screen, and that x1 <= x2?"
   Assumption: Yes, but we should still write robust code that handles edge cases gracefully.
3. Single-Byte Lines: "How should we handle the case where x1 and x2 fall within the exact same byte?"
   Assumption: This is a critical edge case. We must handle it by applying a single combined mask to that specific byte, rather than treating them as separate start and end bytes.

Think About the Solution

Let's design the high-level architecture of our solution. We need to calculate the exact byte indices for our start and end points, and then handle the rendering in three logical phases:

• Phase 1: Calculate Boundaries. Find the byte indices for x1 and x2. Determine the bit offsets for both points.
• Phase 2: Handle the Single-Byte Edge Case. If x1 / 8 == x2 / 8, the entire line fits inside a single byte. We generate a mask that only sets the bits between x1 % 8 and x2 % 8, apply it, and exit early.
• Phase 3: Handle Multi-Byte Lines. If the line spans multiple bytes:
  • Create a start mask to set bits from x1 % 8 to 7, and apply it to the start byte.
  • Fill all intermediate bytes between the start and end bytes with 0xFF.
  • Create an end mask to set bits from 0 to x2 % 8, and apply it to the end byte.

Let's visualize how we construct these masks using bitwise shifts. If we want to set bits from index 3 to 7 in a byte (where index 0 is MSB):

0xFF >>> 3  =>  11111111 >>> 3  =>  00011111

If we want to set bits from index 0 to 5:

~(0xFF >>> (5 + 1))  =>  ~(0xFF >>> 6)  =>  ~(00000011)  =>  11111100

This elegant bitwise math allows us to generate arbitrary masks dynamically without loops!

Write Code and Explain

Here is the complete, production-ready Java implementation. It includes comprehensive comments explaining each bitwise operation.

public class ScreenRenderer {

    /**
     * Draws a horizontal line on a monochrome screen represented as a byte array.
     * 
     * @param screen The byte array representing the screen.
     * @param width  The width of the screen in pixels (divisible by 8).
     * @param x1     The starting x-coordinate of the line.
     * @param x2     The ending x-coordinate of the line.
     * @param y      The y-coordinate of the line.
     */
    public static void drawLine(byte[] screen, int width, int x1, int x2, int y) {
        // Defensive checks to prevent out-of-bounds exceptions
        if (screen == null || width <= 0 || x1 < 0 || x2 < 0 || y < 0) {
            return;
        }
        if (x1 > x2) {
            // Swap x1 and x2 if they are passed in reverse order
            int temp = x1;
            x1 = x2;
            x2 = temp;
        }

        int byteWidth = width / 8;
        int rowOffset = y * byteWidth;

        // Calculate byte indices and bit offsets
        int startByteIdx = x1 / 8;
        int startBitOffset = x1 % 8;
        
        int endByteIdx = x2 / 8;
        int endBitOffset = x2 % 8;

        // Edge Case: The entire line fits within a single byte
        if (startByteIdx == endByteIdx) {
            // Create a mask that sets bits from startBitOffset to endBitOffset
            byte startMask = (byte) (0xFF >>> startBitOffset);
            byte endMask = (byte) ~(0xFF >>> (endBitOffset + 1));
            byte combinedMask = (byte) (startMask & endMask);
            
            screen[rowOffset + startByteIdx] |= combinedMask;
            return;
        }

        // Phase 3: Multi-byte line drawing
        
        // 1. Handle the partial start byte
        if (startBitOffset != 0) {
            // Mask sets bits from startBitOffset to 7
            byte startMask = (byte) (0xFF >>> startBitOffset);
            screen[rowOffset + startByteIdx] |= startMask;
            // The first full byte to write starts at the next index
            startByteIdx++;
        }

        // 2. Handle the partial end byte
        if (endBitOffset != 7) {
            // Mask sets bits from 0 to endBitOffset
            byte endMask = (byte) ~(0xFF >>> (endBitOffset + 1));
            screen[rowOffset + endByteIdx] |= endMask;
            // The last full byte to write ends at the previous index
            endByteIdx--;
        }

        // 3. Fill all intermediate full bytes with 0xFF (all 1s)
        for (int b = startByteIdx; b <= endByteIdx; b++) {
            screen[rowOffset + b] = (byte) 0xFF;
        }
    }
}

Step-by-Step Walkthrough

Let's trace this code with a concrete example. Suppose we have a screen of width 32 (which means 4 bytes per row). We want to draw a line from (3, 2) to (14, 2).

1. Initialization: byteWidth = 4. The row offset for y = 2 is 2 * 4 = 8.
2. Indices & Offsets:
   • startByteIdx = 3 / 8 = 0, startBitOffset = 3 % 8 = 3.
   • endByteIdx = 14 / 8 = 1, endBitOffset = 14 % 8 = 6.
3. Single Byte Check: Since startByteIdx (0) != endByteIdx (1), we bypass the single-byte block.
4. Start Byte Masking: Since startBitOffset (3) != 0, we create startMask = 0xFF >>> 3, which is binary 00011111. We apply this to screen[8 + 0] using bitwise OR (|=). We then increment startByteIdx to 1.
5. End Byte Masking: Since endBitOffset (6) != 7, we create endMask = ~(0xFF >>> 7), which is binary 11111110. We apply this to screen[8 + 1]. We then decrement endByteIdx to 0.
6. Middle Bytes Fill: The loop runs from b = startByteIdx (1) to b = endByteIdx (0). Since 1 <= 0 is false, the loop does not execute. This is correct because our line only spanned two bytes, both of which were partial!

Time & Space Complexity

Let's analyze the efficiency of our optimized solution:

• Time Complexity: O(W / 8) in the worst case, where W is the width of the screen. More accurately, the time complexity is O(B), where B is the number of full bytes spanned by the line. Generating masks and writing partial bytes takes O(1) constant time. Filling the middle bytes takes O(B). This is a massive improvement over the naive O(N) pixel-by-pixel approach, especially for long lines.
• Space Complexity: O(1) auxiliary space. We modify the screen array in-place and only use a few local variables to store indices and masks.

Why This Problem Matters (The Senior Perspective)

This problem is not just an academic exercise; it is a fundamental pattern in systems programming and hardware optimization. Here is why this matters in the real world:

Memory Alignment and Cache Lines

Modern CPUs do not read and write single bits or even single bytes from RAM. They operate on cache lines (typically 64 bytes). When we write code that modifies memory byte-by-byte or word-by-word rather than bit-by-bit, we align our software operations with the physical hardware architecture. This minimizes cache thrashing and maximizes memory bus throughput.

Concurrency and Thread Safety

In a real-world graphics pipeline, multiple threads might be rendering different parts of the screen simultaneously. If two threads attempt to write to different pixels that reside within the same byte, they will cause a race condition (specifically, a write-write conflict). To prevent this, we must either synchronize access to the byte array or partition the screen so that threads only operate on distinct, byte-aligned boundaries.

Final Thoughts

Low-level bit manipulation can feel intimidating at first, but once you break the problem down into byte boundaries and masks, the solution becomes incredibly elegant and highly performant. We moved from a slow, naive pixel-by-pixel loop to a blazing-fast, hardware-friendly byte-aligned writer.

Next time you are faced with a grid or array problem, ask yourself: "Can I group these operations to process them in chunks rather than one by one?" Your CPU (and your users' battery life) will thank you.

Thanks for reading, and happy coding!