Rearrange Products Table - Solution & Explanation

Problem Overview: You are given a Products table where each row contains a product_id and multiple store columns (store1, store2, store3). The task is to transform this wide table into a normalized row format: each non-null store price becomes a separate row with columns product_id, store, and price. This is essentially an unpivot operation commonly seen in database transformations.

Approach 1: Iterative Row and Column Traversal (O(n*k) time, O(1) extra space)

Treat the table like a small matrix: iterate through each product row, then check each store column individually. For every store field (store1, store2, store3), verify whether the value is non-null. When a price exists, emit a new row containing the product_id, the store name, and the price. The key insight is that the number of store columns is fixed and small, so a simple nested traversal works efficiently. This approach maps naturally to languages like Python or C# where you loop through rows and manually construct the output records. Time complexity is O(n*k), where n is the number of products and k is the number of store columns. Extra space is O(1) beyond the output since you only track the current row and column being processed. The pattern resembles iterating over a matrix with conditional filtering.

Approach 2: SQL-like Transformation with Language Features (O(n*k) time, O(k) space)

This approach models the solution after SQL UNPIVOT behavior using built-in language features. Create a small structure (array, map, or list) that pairs store names with their corresponding column values for each row. For example, convert a row into something like [("store1", value1), ("store2", value2), ("store3", value3)]. Iterate through this structure and append an output record whenever the value is not null. Languages like JavaScript or C make this clean by storing the store names in an array and iterating through them dynamically. The main insight is separating column metadata (store names) from row data, which simplifies the transformation logic. Time complexity remains O(n*k) since every product checks every store column. Space complexity is O(k) for the temporary store mapping used during each iteration. This style mirrors transformations commonly used in array-driven data reshaping pipelines.

Recommended for interviews: The iterative row and column traversal approach is typically expected. It clearly shows you understand how to normalize wide data structures by scanning each column and filtering null values. Demonstrating the SQL-style transformation afterward shows deeper familiarity with data reshaping patterns and how unpivot operations are implemented outside SQL engines.