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)

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)

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

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.