Question 3
- A two-dimensional array of integers in which most elements are zero is called a sparse array.
- Memory can be saved by storing only the non-zero values along with their row and column indexes.
- The SparseArrayEntry class is used to represent non-zero elements in a sparse array.
- A SparseArrayEntry object cannot be modified after it has been constructed.
Reflection
This was arguably my hardest FRQ question from this set of questions because I struggled in understanding the SparseArray method and understanding the concept of the value at different coordinates. I will definitely be reviewing FRQs like this in the future in preperation for my AP exam in May.
(a) Write the SparseArray method getValueAt. The method returns the value of the sparse array element at a given row and column in the sparse array. If the list entries contains an entry with the specified row and column, the value associated with the entry is returned. If there is no entry in entries corresponding to the specified row and column, 0 is returned.
import java.util.ArrayList;
class SparseArrayEntry {
private int row;
private int col;
private int value;
public SparseArrayEntry(int row, int col, int value) {
this.row = row;
this.col = col;
this.value = value;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public int getValue() {
return value;
}
}
class SparseArray {
private ArrayList<SparseArrayEntry> entries;
public SparseArray() {
entries = new ArrayList<>();
}
public void addEntry(SparseArrayEntry entry) {
entries.add(entry);
}
public int getValueAt(int row, int col) {
for (SparseArrayEntry e : entries) {
if (e.getRow() == row && e.getCol() == col) {
return e.getValue();
}
}
return 0;
}
}
public class Main {
public static void main(String[] args) {
SparseArray sparse = new SparseArray();
sparse.addEntry(new SparseArrayEntry(1, 1, 3));
sparse.addEntry(new SparseArrayEntry(2, 2, -8));
sparse.addEntry(new SparseArrayEntry(3, 1, -23));
System.out.println("Value at (1, 1): " + sparse.getValueAt(1, 1));
System.out.println("Value at (2, 2): " + sparse.getValueAt(2, 2));
System.out.println("Value at (3, 1): " + sparse.getValueAt(3, 1));
System.out.println("Value at (3, 3): " + sparse.getValueAt(3, 3));
}
}
Main.main(null);
Value at (1, 1): 3
Value at (2, 2): -8
Value at (3, 1): -23
Value at (3, 3): 0
Explanation:
This Java code defines a class SparseArrayEntry representing a single entry in a sparse array, with attributes for row, column, and value. Another class SparseArray maintains a list of sparse array entries and provides methods to add entries and retrieve values at specific row-column indices. The Main class demonstrates the usage by creating a sparse array, adding entries, and retrieving values at various indices, printing the results to the console.
(b) Write the SparseArray method removeColumn. After removing a specified column from a sparsearray:
All entries in the list entries with column indexes matching col are removed from the list.
All entries in the list entries with column indexes greater than col are replaced by entries with column indexes that are decremented by one (moved one column to the left).
The number of columns in the sparse array is adjusted to reflect the column removed.
import java.util.ArrayList;
import java.util.Iterator;
class SparseArrayEntry {
private int row;
private int col;
private int value;
public SparseArrayEntry(int row, int col, int value) {
this.row = row;
this.col = col;
this.value = value;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public int getValue() {
return value;
}
}
class SparseArray {
private ArrayList<SparseArrayEntry> entries;
private int numRows;
private int numCols;
public SparseArray(int numRows, int numCols) {
entries = new ArrayList<>();
this.numRows = numRows;
this.numCols = numCols;
}
public void addEntry(SparseArrayEntry entry) {
entries.add(entry);
}
public void removeColumn(int col) {
Iterator<SparseArrayEntry> iterator = entries.iterator();
while (iterator.hasNext()) {
SparseArrayEntry entry = iterator.next();
if (entry.getCol() == col) {
iterator.remove();
} else if (entry.getCol() > col) {
entry = new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue());
}
}
numCols--;
}
public int getValueAt(int row, int col) {
for (SparseArrayEntry e : entries) {
if (e.getRow() == row && e.getCol() == col) {
return e.getValue();
}
}
return 0;
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
}
public class Main {
public static void main(String[] args) {
SparseArray sparse = new SparseArray(3, 3);
sparse.addEntry(new SparseArrayEntry(1, 1, 3));
sparse.addEntry(new SparseArrayEntry(1, 2, 7));
sparse.addEntry(new SparseArrayEntry(2, 2, -8));
sparse.addEntry(new SparseArrayEntry(3, 1, -23));
sparse.addEntry(new SparseArrayEntry(3, 3, 2));
sparse.removeColumn(2);
System.out.println("Value at (1, 1): " + sparse.getValueAt(1, 1));
System.out.println("Value at (1, 2): " + sparse.getValueAt(1, 2));
System.out.println("Value at (2, 2): " + sparse.getValueAt(2, 2));
System.out.println("Value at (3, 1): " + sparse.getValueAt(3, 1));
System.out.println("Value at (3, 3): " + sparse.getValueAt(3, 3));
System.out.println("NumRows: " + sparse.getNumRows());
System.out.println("NumCols: " + sparse.getNumCols());
}
}
Main.main(null);
Value at (1, 1): 3
Value at (1, 2): 0
Value at (2, 2): 0
Value at (3, 1): -23
Value at (3, 3): 2
NumRows: 3
NumCols: 2
Explanation:
This Java code defines classes to represent a sparse array, where most of the elements are zero. The SparseArray class maintains a list of SparseArrayEntry objects, each representing a non-zero value along with its row and column indices. Additionally, it provides a method removeColumn to remove all entries in a specified column, adjusting the column indices accordingly. The Main class demonstrates the usage by creating a sparse array, adding entries, removing a column, and retrieving values, along with printing the number of rows and columns after modifications.