Structured data types, address calculations, searching, sorting algorithms, Java String & StringBuffer — everything for 100/100.
1D & 2D Arrays
Row/Col Major
Linear & Binary Search
Bubble Sort
Selection Sort
Insertion Sort
Java String Class
StringBuffer
TOPIC 4A
Arrays — 1D
declaration · initialisation · traversal · max/min · sum
An array is a collection of elements of the same data type stored in contiguous memory locations, accessed using a single variable name and an index. Access to any element is O(1) — constant time, regardless of array size.
Fixed Size
Size is declared at creation and cannot change. All elements must be of the same type.
Zero-Indexed
First element is at index 0, last at index n−1 (where n = length).
O(1) Access
Address of element = Base + index × size. Computed directly — no searching needed.
Declaration & Initialisation
Java — Array Syntax
// ── Declaration ─────────────────────────────────────int[] arr; // declares arr as integer arrayint[] arr = newint[5]; // allocates 5 integers, default 0int[] arr = {10, 20, 30, 40, 50}; // declare + initialise// ── Accessing elements ──────────────────────────────
arr[0] = 10; // set first elementint x = arr[2]; // get third element (index 2)int len = arr.length; // get size of array// ── Traversal ───────────────────────────────────────for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
Visual — Array in Memory
int[] arr = {12, 7, 45, 3, 28, 19, 56}
idx 0
12
idx 1
7
idx 2
45
idx 3
3
idx 4
28
idx 5
19
idx 6
56
Common Array Algorithms
Find Maximum
static intfindMax(int[] a) {
int max = a[0]; // assume first is maxfor (int i = 1; i < a.length; i++)
if (a[i] > max)
max = a[i]; // update if larger foundreturn max;
}
Find Minimum
static intfindMin(int[] a) {
int min = a[0]; // assume first is minfor (int i = 1; i < a.length; i++)
if (a[i] < min)
min = a[i]; // update if smaller foundreturn min;
}
Sum & Average
static doubleaverage(int[] a) {
int sum = 0;
for (int x : a) // enhanced for loop
sum += x;
return (double) sum / a.length;
}
Reverse an Array
static voidreverse(int[] a) {
int l=0, r=a.length-1;
while (l < r) {
int t=a[l]; a[l]=a[r]; a[r]=t;
l++; r--;
}
}
TOPIC 4B
Address Calculation
1D formula · 2D row-major · 2D col-major
Arrays are stored in contiguous (sequential) memory locations. Given the base address and element size, the address of any element can be computed directly using a formula — enabling O(1) access.
1D Array Address
// Base = address of arr[0], w = size of each element (bytes)
Address of arr[i]= Base + i × w
Example: Base = 1000, w = 4 bytes (int), find address of arr[5]
Elements are stored column by column. All elements of column 0 come first, then column 1, etc. Used in Fortran and MATLAB (important for ISC theory questions).
// For arr[R][C], element arr[i][j]:
Column Major Address= Base + (j × R + i) × w
// where R = total rows, C = total columns, w = element size
Same example: 3×4 array, Base=200, w=2, find address of arr[2][3] in Column Major
static int[][] add(int[][] A, int[][] B) {
int r = A.length, c = A[0].length;
int[][] C = newint[r][c];
for (int i=0; i<r; i++)
for (int j=0; j<c; j++)
C[i][j] = A[i][j] + B[i][j];
return C;
}
// Matrix Transposestatic int[][] transpose(int[][] A) {
int r=A.length, c=A[0].length;
int[][] T = newint[c][r];
for (int i=0; i<r; i++)
for (int j=0; j<c; j++)
T[j][i] = A[i][j];
return T;
}
TOPIC 4D
Searching
linear search O(n) · binary search O(log n)
Linear Search
static intlinearSearch(int[] a, int key) {
for (int i=0; i<a.length; i++)
if (a[i] == key)
return i; // found at ireturn-1; // not found
}
Works on ANY array (sorted or unsorted)
Time: O(n) worst/average case
Space: O(1)
Best: O(1) if element is first
Binary Search
static intbinarySearch(int[] a, int key) {
int lo=0, hi=a.length-1;
while (lo <= hi) {
int mid = (lo+hi)/2;
if (a[mid]==key) return mid;
if (a[mid]<key) lo = mid+1;
else hi = mid-1;
}
return-1;
}
Array MUST be sorted first
Time: O(log n) — halves each step
Space: O(1) iterative version
For 1000 elements: max 10 steps!
Property
Linear Search
Binary Search
Prerequisite
None
Array must be sorted
Best case
O(1)
O(1)
Worst case
O(n)
O(log n)
Average case
O(n)
O(log n)
n=1000 elements
Up to 1000 comparisons
Up to 10 comparisons
TOPIC 4E
Sorting Algorithms
bubble · selection · insertion — with interactive visualizer
Bubble Sort
Concept
Repeatedly compare adjacent elements and swap them if they are in wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position at the end. Requires n−1 passes for n elements.
Bubble Sort — Java
static voidbubbleSort(int[] a) {
int n = a.length;
for (int i=0; i<n-1; i++) { // n-1 passesfor (int j=0; j<n-1-i; j++) { // inner loop shrinksif (a[j] > a[j+1]) { // out of order?// swap a[j] and a[j+1]int t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
}
Trace: [5, 3, 8, 1, 4]
Pass 1:
5>3 → swap → [3,5,8,1,4]
5<8 → no swap
8>1 → swap → [3,5,1,8,4]
8>4 → swap → [3,5,1,4,8]
Pass 2: → [3,1,4,5,8]
Pass 3: → [1,3,4,5,8]
Pass 4: → [1,3,4,5,8] ✓
Selection Sort
Concept
In each pass, find the minimum element from the unsorted portion and place it at the beginning of the unsorted part. After i passes, the first i elements are sorted. Exactly n−1 swaps — fewer swaps than bubble sort.
Selection Sort — Java
static voidselectionSort(int[] a) {
int n = a.length;
for (int i=0; i<n-1; i++) {
// find minimum in a[i..n-1]int minIdx = i;
for (int j=i+1; j<n; j++)
if (a[j] < a[minIdx])
minIdx = j;
// swap min to position iint t = a[minIdx];
a[minIdx] = a[i];
a[i] = t;
}
}
Trace: [5, 3, 8, 1, 4]
Pass 1: min=1 at idx3, swap a[0]↔a[3]
→ [1, 3, 8, 5, 4]
Pass 2: min=3 at idx1, swap a[1]↔a[1]
→ [1,3, 8, 5, 4]
Pass 3: min=4 at idx4, swap a[2]↔a[4]
→ [1,3,4, 5, 8]
Pass 4: min=5 at idx3, swap a[3]↔a[3]
→ [1,3,4,5,8] ✓
Insertion Sort
Concept
Build the sorted array one element at a time. Pick the next unsorted element and insert it into its correct position among the already-sorted elements by shifting larger elements right. Like sorting playing cards in your hand.
Insertion Sort — Java
static voidinsertionSort(int[] a) {
int n = a.length;
for (int i=1; i<n; i++) {
int key = a[i]; // element to insertint j = i - 1;
// shift larger elements rightwhile (j >= 0 && a[j] > key) {
a[j+1] = a[j];
j--;
}
a[j+1] = key; // insert at correct spot
}
}
Trace: [5, 3, 8, 1, 4]
i=1: key=3, shift 5→ insert 3
→ [3,5, 8, 1, 4]
i=2: key=8, 5<8 no shift
→ [3,5,8, 1, 4]
i=3: key=1, shift 8,5,3 → insert 1
→ [1,3,5,8, 4]
i=4: key=4, shift 8,5 → insert 4
→ [1,3,4,5,8] ✓
Press "Step" to animate one comparison at a time.
Bubble Sort: O(n²) time · O(1) space · Stable ✓
Compare adjacent pairs, swap if out of order. Largest element reaches end each pass.
Sorting Algorithm Complexity
Algorithm
Best
Average
Worst
Space
Stable?
Swaps
Bubble Sort
O(n)
O(n²)
O(n²)
O(1)
Yes
O(n²)
Selection Sort
O(n²)
O(n²)
O(n²)
O(1)
No
O(n)
Insertion Sort
O(n)
O(n²)
O(n²)
O(1)
Yes
O(n²)
⭐ Key Exam Points
Bubble best case O(n): Only with optimised version (flag to detect no swaps in a pass)
Selection always O(n²): Always scans the full unsorted part even if already sorted
Insertion best case O(n): When array is already sorted — inner while loop never executes
Selection minimises swaps: Useful when writes are expensive
In Java, String is a class in java.lang. Strings are immutable — once created, their content cannot be changed. Any "modification" creates a new String object.
String s = "Hello";
s = s + " World"; // new object!// Original "Hello" still exists// s now points to new "Hello World"// Use StringBuffer for heavy edits// (see next section)
String Methods — Complete Reference
length()
"Hello".length() → 5
Returns the number of characters in the string. Zero-indexed internally but length() counts from 1.
charAt(int i)
"Hello".charAt(1) → 'e'
Returns the character at index i. Index starts at 0. Throws StringIndexOutOfBoundsException if i is invalid.
substring(int s)
"Hello".substring(2) → "llo"
Returns substring from index s to end of string (inclusive of s).
substring(int s, int e)
"Hello".substring(1,4) → "ell"
Returns substring from index s (inclusive) to index e (exclusive). Length = e − s.
indexOf(char/String)
"Hello".indexOf('l') → 2
Returns first index of the character or substring. Returns −1 if not found.
lastIndexOf(char/String)
"Hello".lastIndexOf('l') → 3
Returns last (rightmost) occurrence index. Returns −1 if not found.
equals(String s)
"Hi".equals("hi") → false
Returns true if strings have same characters with same case. Use this, NOT ==, for string comparison in Java.
equalsIgnoreCase(String)
"Hi".equalsIgnoreCase("hi") → true
Case-insensitive comparison. Returns true if strings are equal ignoring case.
compareTo(String s)
"abc".compareTo("abd") → -1
Lexicographic comparison. Returns 0 if equal, negative if calling string comes before, positive if after.
toLowerCase()
"Hello".toLowerCase() → "hello"
Returns new string with all characters converted to lowercase. Original unchanged (immutable).
toUpperCase()
"hello".toUpperCase() → "HELLO"
Returns new string with all characters converted to uppercase.
trim()
" hi ".trim() → "hi"
Returns string with leading and trailing whitespace removed.
replace(old, new)
"aabb".replace('a','x') → "xxbb"
Replaces ALL occurrences of old char/substring with new char/substring. Returns new String.
concat(String s)
"Hi".concat(" World") → "Hi World"
Concatenates s to end of calling string. Same as + operator. Returns new String.
startsWith(String)
"Hello".startsWith("He") → true
Returns true if the string starts with the given prefix.
endsWith(String)
"Hello".endsWith("lo") → true
Returns true if the string ends with the given suffix.
contains(CharSequence)
"Hello".contains("ell") → true
Returns true if the string contains the given sequence anywhere.
toCharArray()
"Hi" → {'H','i'}
Converts string to a char array. Useful for character-by-character processing.
valueOf(int/double/...)
String.valueOf(42) → "42"
Static method. Converts primitive or object to its String representation.
isEmpty()
"".isEmpty() → true
Returns true if length() == 0. Does not handle null.
String is immutable — every modification creates a new object. In loops with heavy string manipulation, this wastes memory and time. StringBuffer is mutable — it can be modified in-place without creating new objects. Use StringBuffer when you need to do many string concatenations or modifications.
String (Immutable)
// BAD — creates many String objectsString result = "";
for (int i=0; i<1000; i++) {
result = result + i; // new object each time!
}
// 1000 String objects created// Slow and memory-wasteful
StringBuffer (Mutable)
// GOOD — modifies in-placeStringBuffer sb = newStringBuffer();
for (int i=0; i<1000; i++) {
sb.append(i); // modifies same object
}
String result = sb.toString();
// Single object, much faster!
StringBuffer Methods
append(value)
sb.append("Java") → adds "Java" at end
Appends the string representation of any type (int, char, boolean, String, etc.) to the end. Returns the same StringBuffer (chainable).
insert(int i, value)
sb.insert(2,"XY") → inserts at index 2
Inserts value starting at index i. Characters after i shift right. Returns same StringBuffer.
delete(int s, int e)
sb.delete(1,4) → removes indices 1,2,3
Deletes characters from index s (inclusive) to e (exclusive). Returns same StringBuffer.
deleteCharAt(int i)
sb.deleteCharAt(3) → removes char at 3
Removes the character at specified index. All subsequent characters shift left.
reverse()
sb("Hello").reverse() → "olleH"
Reverses the entire character sequence in-place. Very useful for palindrome checks.
replace(s, e, str)
sb.replace(0,2,"XY")
Replaces characters from index s to e (exclusive) with the given string.
charAt(int i)
sb.charAt(0) → first char
Returns character at index i. Same behaviour as String.charAt().
setCharAt(int i, char c)
sb.setCharAt(0,'Z') → changes char at 0
Sets the character at index i to c. Modifies in-place (not possible with String!).
length()
sb.length() → current length
Returns current number of characters (not capacity).
toString()
sb.toString() → String object
Converts StringBuffer to an immutable String object. Use at the end when you're done modifying.
Q1. For a 1D array with Base=1000, element size=4 bytes, what is the address of arr[7]?
Address = Base + i × w = 1000 + 7 × 4 = 1000 + 28 = 1028.
Q2. In a 4×5 matrix (Row Major, 4 rows, 5 cols), Base=200, w=2, what is the address of arr[2][3]?
Row Major: B + (i×C + j)×w = 200 + (2×5 + 3)×2 = 200 + 13×2 = 200 + 26 = 226. Wait — C=5 (columns), so: 200+(2×5+3)×2 = 200+13×2 = 200+26 = 226. Let me recheck with C=5: 2×5=10, 10+3=13, 13×2=26, 200+26=226. Hmm, let me verify with the answer: (2×5+3)×2 = 13×2=26, so address=226. The correct answer should be 226. Let me re-examine: 200 + (2*5 + 3)*2 = 200 + 26 = 226. So the correct option is 226.
Q3. What does "Hello World".substring(6, 11) return?
"Hello World": indices 0-10. substring(6,11) extracts indices 6,7,8,9,10 = 'W','o','r','l','d' = "World". Remember: end index is EXCLUSIVE in Java.
Q4. Which sorting algorithm performs the fewest swaps?
Selection Sort performs at most n−1 swaps (one per pass — swaps the minimum to its position). Bubble and Insertion can perform O(n²) swaps in the worst case. Selection is preferred when writes/swaps are expensive.
Q5. What is the output of: new StringBuffer("racecar").reverse().toString()?
"racecar" reversed is still "racecar" — it's a palindrome! The reverse() method reverses in-place, but since the string reads the same forwards and backwards, the result is identical.
Q6. What is the time complexity of accessing an element in an array by index?
Array access is O(1) — constant time. Using the formula Address = Base + index × size, the address is computed directly in one arithmetic operation, regardless of array size. This is a key advantage of arrays over linked lists.
Q7. What is the best case time complexity of Insertion Sort?
Insertion Sort best case is O(n) — when the array is already sorted. The outer loop runs n−1 times, but the inner while loop never executes (no element is greater than the key to its left). So only n−1 comparisons are made.
Q8. Which is the key difference between String and StringBuffer?
The fundamental difference: String is immutable (cannot be modified after creation — any operation returns a new object), while StringBuffer is mutable (modifications happen in-place on the same object). Use StringBuffer for heavy string manipulation to avoid memory waste.
REF
Cheat Sheet
1D Address
B + i × w
Base + index × size
Row Major
B + (i×C + j) × w
Java default
Col Major
B + (j×R + i) × w
Fortran/MATLAB
Array Access
O(1) constant time
Direct address calculation
Linear Search
O(n) worst case
No sorting needed
Binary Search
O(log n)
Sorted array required
Bubble Sort
O(n²) avg/worst
Stable, O(n²) swaps
Selection Sort
O(n²) always
Only O(n) swaps
Insertion Sort
O(n) best, O(n²) worst
Best for nearly sorted
String.substring
s(start, end)
end is EXCLUSIVE
String.charAt
s.charAt(i)
0-indexed
String.indexOf
returns -1 if not found
First occurrence
String.compareTo
0 = equal, <0, >0
Lexicographic order
StringBuffer.append
sb.append(x)
Adds to end
StringBuffer.reverse
sb.reverse()
In-place reversal
Immutability
String = immutable
StringBuffer = mutable
🎯 Top ISC Exam Questions — Arrays & Strings
Calculate the address of element arr[i][j] using Row Major / Column Major formula
Write and trace Bubble Sort / Selection Sort / Insertion Sort on a given array
Find the output of given String method calls (substring, indexOf, charAt, compareTo)
Write Java code to find max/min/sum of array elements
Compare String vs StringBuffer with examples
Write a program using StringBuffer methods (append, insert, delete, reverse)
Trace Binary Search on a given sorted array for a given key
Write a program to count vowels/consonants/words in a string