Go Defragmentation Challenge: Optimizing Contiguous Memory Blocks

Imagine a simplified memory management system where data is stored in blocks, and these blocks can become fragmented over time, leading to inefficient access. Your task is to implement a defragmentation algorithm that consolidates these blocks into contiguous segments, improving memory utilization and performance. This is a fundamental concept in operating systems and storage management, crucial for efficient data handling.

Problem Description

You are given a slice of integers representing memory blocks. Each integer represents the size of a contiguous memory block. Some blocks might have a size of 0, indicating free space. Your goal is to implement a function defragment(memory []int) that rearranges these blocks in-place such that all non-zero blocks are moved to the beginning of the slice, followed by all zero blocks (representing free space). The relative order of the non-zero blocks should be preserved.

Key Requirements:

1. In-place Modification: The defragmentation must occur directly within the input memory slice. No new slices should be created to store the defragmented data, except for temporary variables for swapping.
2. Preserve Non-Zero Order: The relative order of the non-zero memory blocks must be maintained. If block A appears before block B in the original slice and both are non-zero, block A should still appear before block B after defragmentation.
3. Consolidate Free Space: All zero-sized blocks (free space) should be moved to the end of the slice.
4. Return Value: The function should return the modified memory slice.

Expected Behavior:

After calling defragment(memory), the slice should be structured as: [non-zero block 1, non-zero block 2, ..., non-zero block N, 0, 0, ..., 0].

Edge Cases:

• An empty input slice.
• A slice containing only zero-sized blocks.
• A slice containing only non-zero blocks.
• A slice with mixed zero and non-zero blocks in various orders.

Examples

Example 1:

Input: []int{2, 0, 5, 0, 3, 0, 1}
Output: []int{2, 5, 3, 1, 0, 0, 0}
Explanation: The non-zero blocks (2, 5, 3, 1) are moved to the beginning, maintaining their original relative order. The zero blocks are consolidated at the end.

Example 2:

Input: []int{0, 0, 0, 10, 20, 0, 30}
Output: []int{10, 20, 30, 0, 0, 0, 0}
Explanation: All non-zero blocks are placed at the front, preserving their order (10, 20, 30). The remaining slots are filled with zeros.

Example 3:

Input: []int{5, 10, 15}
Output: []int{5, 10, 15}
Explanation: The slice is already defragmented. No changes are needed.

Example 4:

Input: []int{0, 0, 0}
Output: []int{0, 0, 0}
Explanation: The slice consists only of free space. No changes are needed.

Constraints

• The input memory slice can contain between 0 and 1000 elements.
• Each element in memory will be an integer between 0 and 100 (inclusive).
• The algorithm should aim for an efficient time complexity, ideally O(n), where n is the number of elements in the slice.

Notes

Consider how you can iterate through the slice and keep track of the position where the next non-zero block should be placed. Think about the swaps required to move elements without losing data or disrupting the order of non-zero elements. This problem is a classic example of a "two-pointer" approach or a variation thereof.