Select a suitable data structure (1D or 2D array) to use for a given task

Topic 10.2 – Arrays

Learning Objective (AO2)

Analyse a problem, select the most suitable array structure (1‑D or 2‑D) and justify the choice.

---

1. Cambridge‑Specific Syntax

---

2. Syllabus Terminology (AS Level)

Term	Definition (Cambridge)	Typical Use in Pseudocode
Lower‑bound	Smallest valid index (always 0 in Cambridge exams).	FOR i ← 0 TO n‑1
Upper‑bound	Largest valid index; for an array of size n it is n‑1.	FOR i ← 0 TO n‑1
Index	Integer used to locate an element; written as i (1‑D) or i, j (2‑D).	value ← array[i] or value ← matrix[i][j]
Size	Number of elements an array can hold. For a 2‑D array the size is rows × columns.	DECLARE scores[0…9] : INTEGER // size = 10

---

3. Declaration & Initialisation

3.1 Pseudocode (exam‑required)

DECLARE temps[0…29] : REAL               // 1‑D array, 30 elements
DECLARE marks[0…29][0…5] : INTEGER        // 2‑D array, 30×6 elements

3.2 Java (example language)

double[] temps = new double[30];               // 1‑D
int[][] marks = new int[30][6];                // 2‑D

3.3 Python (optional for comparison)

# 1‑D
temps = [0.0] * 30

# 2‑D (list of lists)
marks = [[0] * 6 for _ in range(30)]

Each declaration mirrors the pseudocode, helping you translate between the exam language and a real programming language.

3.4 Common Exam Pitfalls (AO1)

• Using 1‑based indexing (e.g., FOR i ← 1 TO n) – Cambridge always expects 0‑based.
• Forgetting the upper‑bound (size‑1) when writing loop limits.
• Declaring the wrong number of dimensions for the data (e.g., a table stored in a 1‑D array without a conversion formula).
• Omitting the colon and type in the declaration (e.g., DECLARE a[0…9] instead of DECLARE a[0…9] : INTEGER).

---

4. Selecting a 1‑D or 2‑D Array (AO2)

4.1 Decision Checklist (mapped to AO2 wording)

Checklist Item (What you must analyse)	AO2 Requirement (Syllabus wording)	Guiding Question
Identify the logical dimensions of the data.	“Analyse the problem and decide the most suitable array structure.”	Is the data a simple list or a table?
Determine the number of indices needed to locate an element.	“Select the most suitable array type and justify the choice.”	Can every item be described with one number (day, position) or do you need a pair (row & column)?
Consider future extensions or alternative processing.	“Justify the choice of array structure.”	Will you ever need to treat the data as a linear list (flatten) or as a grid?
Check memory and performance implications.	“Analyse the problem and select the most suitable array structure.”	Does the extra dimension add unnecessary mental overhead?

4.2 When to Choose a 1‑D Array

• Data represents a linear sequence (e.g., daily temperatures, characters of a word, scores of a single game).
• Each element can be identified with a single index i.
• Memory layout is a single contiguous block of n elements.

4.3 When to Choose a 2‑D Array

• Data naturally forms rows and columns – tables, matrices, grids (e.g., chessboard, image pixels, marks of many students).
• Two indices i (row) and j (column) are required to locate an element.
• Algorithms that operate row‑wise or column‑wise (matrix multiplication, Sudoku validation) become clearer.

---

5. Comparison Table

Criterion	1‑D Array	2‑D Array
Indexing	Single index i	Two indices i, j
Typical Use‑case	Lists, queues, simple vectors	Grids, matrices, tables
Memory layout	Linear block of n elements	Linear block of rows × columns (row‑major or column‑major)
Complexity of access	O(1) using array[i]	O(1) using matrix[i][j] (after offset calculation)
Declaration (Java)	int[] scores = new int[10];	int[][] board = new int[8][8];

---

6. Processing Arrays (Reading, Writing, Traversing, Searching, Sorting)

6.1 Reusable Bounds‑Checking Pattern (AO1)

// Safe access pattern (pseudocode)
IF i < 0 OR i ≥ size THEN
    OUTPUT "Error: index out of bounds"
ELSE
    // read or write here
END IF

6.2 Reading & Writing an Element

// Pseudocode – increase the 5th temperature by 2.5°C
IF 4 >= 0 AND 4 < 30 THEN
    temps[4] ← temps[4] + 2.5
END IF

// Java
if (4 >= 0 && 4 < temps.length) {
    temps[4] = temps[4] + 2.5;
}

6.3 Traversal (Linear Scan)

// 1‑D – print all temperatures
FOR i ← 0 TO 29 DO
    OUTPUT temps[i]
END FOR

// 2‑D – row‑wise traversal of a 5×4 scores table
FOR i ← 0 TO 4 DO
    FOR j ← 0 TO 3 DO
        OUTPUT scores[i][j] + " "
    END FOR
    OUTPUT NEWLINE
END FOR

6.4 Linear Search (1‑D)

// Find the first occurrence of 85 in a marks array
DECLARE position ← -1
FOR i ← 0 TO n‑1 DO
    IF marks[i] = 85 THEN
        position ← i
        EXIT FOR
    END IF
END FOR
// position = -1 means “not found”

6.5 Bubble‑Sort (1‑D)

FOR pass ← 0 TO n‑2 DO
    FOR i ← 0 TO n‑2‑pass DO
        IF array[i] > array[i+1] THEN
            // swap
            temp ← array[i]
            array[i] ← array[i+1]
            array[i+1] ← temp
        END IF
    END FOR
END FOR

6.6 Row‑wise Update of a 2‑D Array

// Add 5 bonus points to every player’s score in game 2 (column index 1)
FOR i ← 0 TO rows‑1 DO
    scores[i][1] ← scores[i][1] + 5
END FOR

---

7. Relationship Between 1‑D and 2‑D Arrays

A 2‑D array can be simulated with a 1‑D array using a conversion formula. This is useful when a language only supports 1‑D structures or when an API expects a flat list.

• Assume rows = m, cols = n (row‑major order).
• Conversion (2‑D → 1‑D): k = i × n + j
• Reverse conversion (1‑D → 2‑D): i = k ÷ n, j = k mod n

// Pseudocode – accessing element (i, j) in a flattened 1‑D array
k ← i * n + j
value ← flatArray[k]

---

8. Illustrative Examples

Example 1 – Weekly Temperatures (1‑D)

Task: Store the temperature for each of the 30 days in a month.

// Pseudocode
DECLARE temps[0…29] : REAL
FOR d ← 0 TO 29 DO
    INPUT temps[d]
END FOR

Justification: Each temperature is identified by a single day number → 1‑D array.

Example 2 – Marks of 30 Students in 6 Subjects (2‑D)

// Java declaration
int[][] marks = new int[30][6];   // marks[student][subject]

// Row‑wise input
FOR s ← 0 TO 29 DO
    FOR sub ← 0 TO 5 DO
        INPUT marks[s][sub]
    END FOR
END FOR

Justification: Data forms a table (students × subjects) → 2‑D array.

Example 3 – Simulating a 3×4 Matrix with a 1‑D Array

DECLARE flat[0…11] : INTEGER   // 3×4 = 12 elements
DECLARE rows ← 3, cols ← 4

// Set element (2,1) to 99 (row‑major)
k ← 2 * cols + 1          // k = 2*4 + 1 = 9
flat[k] ← 99

---

9. Practice Questions

1. Which array type would you use to store the characters of a single word entered by a user? Justify your choice.
2. A school wants to record the marks of 30 students in 6 subjects. Choose the appropriate array structure and write a declaration in:
   • Pseudocode
   • Java
3. Explain how a 2‑D array can be simulated using a 1‑D array. Provide the conversion formula for row‑major order and give a short pseudocode example.
4. Write pseudocode to perform a linear search for the value 75 in a 1‑D array called scores of size n. Include bounds checking.
5. Show how to traverse a 3×4 matrix and increase every element by 10. Use pseudocode.

10. Answer Key (Teacher Use)

1. 1‑D array; a word is a linear sequence of characters, each accessed by its position (single index).
2. • Pseudocode: DECLARE marks[0…29][0…5] : INTEGER
   • Java: int[][] marks = new int[30][6];
3. Use a 1‑D array of size rows × cols. Conversion (row‑major): k = i * cols + j.

   // Access (i, j) in a flat array
   k ← i * cols + j
   value ← flatArray[k]
   

4. DECLARE position ← -1
   FOR i ← 0 TO n‑1 DO
       IF i < 0 OR i ≥ n THEN
           OUTPUT "Index error"
           EXIT FOR
       END IF
       IF scores[i] = 75 THEN
           position ← i
           EXIT FOR
       END IF
   END FOR
   

5. FOR i ← 0 TO 2 DO          // rows
       FOR j ← 0 TO 3 DO      // columns
           matrix[i][j] ← matrix[i][j] + 10
       END FOR
   END FOR
   

---

11. Summary

• Use a 1‑D array for linear data; each element needs only one index.
• Use a 2‑D array for tabular or grid‑like data; each element needs a row and column index.
• Remember that the lower‑bound is always 0 and the upper‑bound is size‑1 in Cambridge exams.
• When writing loops or performing reads/writes, always apply the reusable bounds‑checking pattern.
• Be comfortable translating between pseudocode, Java, and Python, and know how to simulate a 2‑D array with a 1‑D array when required.
• Practice the common processing tasks (traversal, search, sort, update) – they are directly examined in the Cambridge 9618 exam.