Unit 1: Basic Data Structures - Subjective Questions

An array is a linear data structure that stores a collection of elements of the same data type in contiguous memory locations, accessed using an index.

1D Array Declaration:
c
int arr[5] = {10, 20, 30, 40, 50};

• Elements are accessed as arr[0] to arr[4].
• Processing (traversal):
  c
  for(int i = 0; i < 5; i++)
  printf("%d ", arr[i]);

2D Array Declaration:
c
int mat[3][3] = {{1,2,3},{4,5,6},{7,8,9}};

• Stored in row-major order in most languages.
• Address of mat[i][j] = , where is number of columns.

Processing a 2D array:
c
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
printf("%d ", mat[i][j]);

Key Points:

• Access time is due to index-based addressing.
• Fixed size once declared (static arrays).

Insertion in an Array:
To insert an element at position pos, all elements from pos to the end must shift one place right.

for(int i = n; i > pos; i--)
    arr[i] = arr[i-1];
arr[pos] = key;
n++;

- **Time Complexity:** $O(n)$ in worst case (insert at beginning).

Deletion from an Array:
To delete an element at position pos, all elements after it shift one place left.

for(int i = pos; i < n-1; i++)
    arr[i] = arr[i+1];
n--;

- **Time Complexity:** $O(n)$ in worst case (delete from beginning).

Summary:

• Both operations require shifting, making them costly.
• Access remains , but structural changes are .
• This limitation motivates the use of linked lists for frequent insertions/deletions.

Array rotation means shifting array elements left or right by positions.

1. Reversal Algorithm (Left Rotation by d):

• Reverse first elements.
• Reverse remaining elements.
• Reverse the whole array.

reverse(arr, 0, d-1);
reverse(arr, d, n-1);
reverse(arr, 0, n-1);

- **Time:** $O(n)$, **Space:** $O(1)$.

Example: [1,2,3,4,5],

• After step 1: [2,1,3,4,5]
• After step 2: [2,1,5,4,3]
• After step 3: [3,4,5,1,2]

2. Juggling Algorithm:

• Divide array into sets.
• Move elements within each set to their rotated positions.
• Time: , Space: .

3. Temporary Array Method:

• Copy first elements to a temp array, shift rest, append temp.
• Time: , Space: .

The Reversal method is most commonly preferred for its simplicity and space.

Condition for Multiplication:
Two matrices and can be multiplied only if the number of columns of A equals the number of rows of B. The result is .

Formula:

Algorithm:
c
for(int i = 0; i < m; i++)
for(int j = 0; j < p; j++) {
C[i][j] = 0;
for(int k = 0; k < n; k++)
C[i][j] += A[i][k] * B[k][j];
}

Time Complexity Derivation:

• Outer loops run times.
• Inner loop runs times for each.
• Total operations = .
• Time Complexity: , or for square matrices.
• Space Complexity: for the result matrix.

Lower Triangular Matrix:
A square matrix where all elements above the main diagonal are zero, i.e., for all .

for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    if(i < j && A[i][j] != 0) isLower = false;

Upper Triangular Matrix:
A square matrix where all elements below the main diagonal are zero, i.e., for all .

for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    if(i > j && A[i][j] != 0) isUpper = false;

Key Differences:

Both must be square matrices and the diagonal may contain non-zero values.

Spiral Order Traversal prints matrix elements in a spiral: top row → right column → bottom row → left column, moving inward.

Algorithm using four boundaries (top, bottom, left, right):
c
int top=0, bottom=m-1, left=0, right=n-1;
while(top<=bottom && left<=right){
for(int i=left;i<=right;i++) print(A[top][i]);
top++;
for(int i=top;i<=bottom;i++) print(A[i][right]);
right--;
if(top<=bottom){
for(int i=right;i>=left;i--) print(A[bottom][i]);
bottom--;
}
if(left<=right){
for(int i=bottom;i>=top;i--) print(A[i][left]);
left++;
}
}

Example:

Output: 1 2 3 6 9 8 7 4 5

Complexity:

• Time: — each element visited once.
• Space: — only boundary variables used.

Problem: Find elements that appear in every row of an matrix.

Efficient Approach using Hashing:

1. Insert all elements of the first row into a hash map with count = 1.
2. For each subsequent row, for every element, if it exists in the map with count equal to current row index, increment it (ensures counted once per row).
3. After processing all rows, elements whose count equals (number of rows) are common to all.

Pseudocode:
c
map<int,int> h;
for(int j=0;j<n;j++) h[A[0][j]] = 1;
for(int i=1;i<m;i++)
for(int j=0;j<n;j++)
if(h[A[i][j]] == i) h[A[i][j]] = i+1;
for(auto p : h)
if(p.second == m) print(p.first);

Complexity:

• Time: using hash map (average).
• Space: for the hash map.

Improvement: A naive approach comparing rows takes ; hashing reduces it to linear by providing average lookups.

A string is an array of characters terminated by a null character '\0'.

Declaration:
c
char str1[] = "Hello";
char str2[20];
char *str3 = "World";

Common String Functions (string.h):

• strlen(s) — returns length excluding '\0'.
• strcpy(dest, src) — copies src into dest.
• strcat(dest, src) — concatenates src to dest.
• strcmp(s1, s2) — compares two strings; returns 0 if equal.
• strrev(s) — reverses a string.

Example:
c
char a[20] = "Hello";
char b[] = " World";
strcat(a, b); // a = "Hello World"
printf("%d", strlen(a)); // 11

Manipulation Tasks:

• Reversing, converting case, checking palindrome, counting vowels.
• Strings are mutable when declared as char arrays but string literals (char*) should not be modified.

A Pangram is a sentence containing every letter of the English alphabet at least once (a–z).

Problem: Find the missing characters required to make a string a pangram.

Algorithm:

1. Create a boolean array seen[26] initialized to false.
2. Traverse the string; for each alphabet character, mark seen[c - 'a'] = true.
3. After traversal, all indices still false correspond to missing letters.
4. Collect and return those characters.

Pseudocode:
c
bool seen[26] = {false};
for(char c : str)
if(isalpha(c)) seen[tolower(c)-'a'] = true;
for(int i=0;i<26;i++)
if(!seen[i]) print((char)('a'+i));

Example:
Input: "the quick brown fox"
Missing letters: a d g j l m p s v y z etc. (all not present).

Complexity:

• Time:
• Space:

If no letters are missing, the string is already a pangram.

Problem: Rearrange characters of a string such that no two adjacent characters are identical. If impossible, return an indication.

Key Condition:
Rearrangement is possible only if the frequency of the most frequent character , where is string length.

Greedy Algorithm using Max-Heap:

1. Count frequency of each character.
2. Build a max-heap (priority queue) ordered by frequency.
3. Repeatedly extract the two most frequent characters, append them to the result, decrement their counts, and re-insert if count > 0.
4. Handle the last remaining character carefully.

Pseudocode:
c
priority_queue<pair<int,char>> pq; // freq, char
while(pq.size() > 1){
auto a = pq.top(); pq.pop();
auto b = pq.top(); pq.pop();
result += a.char; result += b.char;
if(--a.freq > 0) pq.push(a);
if(--b.freq > 0) pq.push(b);
}
if(!pq.empty()){
if(pq.top().freq > 1) return "Not Possible";
result += pq.top().char;
}

Complexity:

• Time: where = distinct characters.
• Space: .

Anagram: Two strings are anagrams if they contain the same characters with the same frequencies.

Problem: Find the minimum number of deletions needed so that two strings become anagrams of each other.

Algorithm:

1. Compute frequency counts of both strings using two arrays of size 26.
2. For each character, the number of deletions required is the absolute difference of frequencies.
3. Sum these differences.

Formula:

Pseudocode:
c
int c1[26]={0}, c2[26]={0};
for(char ch : s1) c1[ch-'a']++;
for(char ch : s2) c2[ch-'a']++;
int result = 0;
for(int i=0;i<26;i++)
result += abs(c1[i]-c2[i]);

Example:
s1 = "bcadeh", s2 = "hea"
Extra in s1: b, c, d → 3 deletions. Total = 3.

Complexity:

• Time:
• Space:

A stack is a LIFO (Last In First Out) data structure. Using an array, a variable top tracks the index of the topmost element.

Initialization: top = -1 (empty stack).

PUSH Operation:
c
if(top == MAX-1)
printf("Stack Overflow");
else
stack[++top] = x;

• Overflow: occurs when top == MAX-1.

POP Operation:
c
if(top == -1)
printf("Stack Underflow");
else
x = stack[top--];

• Underflow: occurs when top == -1.

PEEK/TOP Operation:
c
if(top == -1)
printf("Stack Empty");
else
return stack[top];

Complexity: All operations are .

Limitations:

• Fixed size due to static array.
• Can waste memory or cause overflow — dynamic arrays or linked lists overcome this.

Objective: Use a single array to implement two stacks such that space is fully utilized and overflow occurs only when the array is completely full.

Efficient Approach (Two ends):

• Stack 1 grows from the left end (index 0 upward), with top1 starting at -1.
• Stack 2 grows from the right end (index n-1 downward), with top2 starting at n.
• Overflow occurs only when top1 + 1 == top2 (they meet).

Operations:
c
// Push to stack1
if(top1 + 1 < top2) arr[++top1] = x;
else overflow;

// Push to stack2
if(top1 + 1 < top2) arr[--top2] = x;
else overflow;

// Pop stack1
if(top1 >= 0) x = arr[top1--];
else underflow;

// Pop stack2
if(top2 < n) x = arr[top2++];
else underflow;

Advantage:

• Full space utilization: overflow only when combined size = n.
• All operations remain .

This is superior to dividing the array into two fixed halves, which wastes space if one stack fills faster.

A stack (LIFO) can be simulated using queues (FIFO). Two common approaches exist using two queues q1 and q2.

Approach 1 — Push Costly (making enqueue expensive):

• Push(x):
  1. Enqueue x into q2.
  2. Dequeue all elements from q1 and enqueue into q2.
  3. Swap q1 and q2.
• Pop: dequeue from q1.
• Time: Push , Pop .

Approach 2 — Pop Costly (making dequeue expensive):

• Push(x): enqueue directly into q1.
• Pop:
  1. Move all but the last element from q1 to q2.
  2. Dequeue the last element (this is the popped value).
  3. Swap q1 and q2.
• Time: Push , Pop .

Single Queue Variant (Push Costly):

• Enqueue x, then rotate the queue by dequeuing and re-enqueuing all previous elements so x moves to front.

Complexity Summary:

A Circular Queue is a linear data structure that connects the last position back to the first, forming a circle. This overcomes the memory wastage problem of linear queues.

Structure: Uses front, rear, and array of size n. Indices wrap using modulo.

Enqueue (Insert):
c
if((rear+1) % n == front)
printf("Queue Full");
else {
if(front == -1) front = 0;
rear = (rear + 1) % n;
queue[rear] = x;
}

Dequeue (Delete):
c
if(front == -1)
printf("Queue Empty");
else {
x = queue[front];
if(front == rear) front = rear = -1;
else front = (front + 1) % n;
}

Full Condition: (rear + 1) % n == front
Empty Condition: front == -1

Advantages over Linear Queue:

• In a linear queue, once rear reaches the end, no insertion is possible even if front slots are free (false overflow).
• A circular queue reuses vacated spaces, ensuring efficient memory utilization.

Complexity: Enqueue and Dequeue are .

A Deque is a generalized queue allowing insertion and deletion at both front and rear ends. Using a circular array prevents false overflow.

Operations:

• insertFront(x)
• insertRear(x)
• deleteFront()
• deleteRear()
• getFront() / getRear()

insertFront:
c
if(full) return;
if(front == -1) front = rear = 0;
else front = (front - 1 + n) % n;
arr[front] = x;

insertRear:
c
if(full) return;
if(front == -1) front = rear = 0;
else rear = (rear + 1) % n;
arr[rear] = x;

deleteFront:
c
if(empty) return;
if(front == rear) front = rear = -1;
else front = (front + 1) % n;

deleteRear:
c
if(empty) return;
if(front == rear) front = rear = -1;
else rear = (rear - 1 + n) % n;

Full Condition: (rear+1)%n == front

Applications:

• Implementing both stacks and queues.
• Sliding window problems (max/min in a window).
• Undo operations, palindrome checking, job scheduling.

Complexity: All operations run in .

The Two Pointer Technique uses two index variables that move toward or away from each other to solve problems efficiently, often reducing brute force to or .

Problem: Find if any pair in an array sums to .

Approach 1 — Sort + Two Pointers:

1. Sort the array.
2. Set left = 0, right = n-1.
3. While left < right:
   • If arr[left] + arr[right] == X → pair found.
   • If sum < X → left++.
   • If sum > X → right--.

sort(arr, arr+n);
int l=0, r=n-1;
while(l < r){
  int sum = arr[l] + arr[r];
  if(sum == X) return true;
  else if(sum < X) l++;
  else r--;
}
return false;

- **Time:** $O(n \log n)$ (due to sorting), **Space:** $O(1)$.

Approach 2 — Hashing (for unsorted, no sort needed):

• For each element, check if X - arr[i] exists in a hash set.
• Time: , Space: .

The two-pointer method is space-efficient, while hashing is faster if sorting is undesirable.

A Peak Element is an element that is greater than or equal to its neighbors. For array arr, arr[i] is a peak if arr[i] >= arr[i-1] and arr[i] >= arr[i+1]. Boundary elements consider only one neighbor.

Note: An array may have multiple peaks; we only need to find any one.

Efficient Approach — Binary Search ():
Since we only need one peak, we exploit the property that moving toward the larger neighbor always leads to a peak.

int low = 0, high = n-1;
while(low < high){
  int mid = (low + high) / 2;
  if(arr[mid] < arr[mid+1])
    low = mid + 1;   // peak lies to the right
  else
    high = mid;      // peak lies to the left (incl mid)
}
return low; // index of a peak

Explanation:

• If arr[mid] < arr[mid+1], an ascending slope guarantees a peak on the right.
• Otherwise, a peak exists on the left side (including mid).

Complexity:

• Time: using binary search.
• Space: .
• A linear scan would take .

Part A — Rearrange Positive and Negative Numbers Alternately:
Goal: place elements so signs alternate (e.g., +, -, +, -, ...).

Approach (using extra space):

1. Separate positives and negatives into two lists.
2. Merge them alternately back into the array.

// place negatives at even index and positives at odd (or vice versa)
int posIdx = 1, negIdx = 0;
// fill alternately from separated lists

- **Time:** $O(n)$, **Space:** $O(n)$.
- An in-place variant exists but is more complex.

Part B — Majority Element (Moore's Voting Algorithm):
A majority element appears more than times.

Steps:

1. Find Candidate: Maintain count and candidate. If count is 0, pick current as candidate. Increment if same, else decrement.
2. Verify: Count occurrences of candidate to confirm it exceeds .

int count = 0, cand = -1;
for(int i=0;i<n;i++){
  if(count == 0) cand = arr[i];
  count += (arr[i] == cand) ? 1 : -1;
}
// verify cand by recounting

Complexity: time, space. This is optimal compared to hashing ( space) or sorting ().

(a) Move All Zeros to End of Array:
Rearrange so all non-zero elements retain their relative order at the front and zeros move to the end.

Two-Pointer Approach:

1. Maintain a pointer j for the position of the next non-zero element.
2. Traverse the array; whenever a non-zero element is found, place it at index j and increment j.
3. Fill remaining positions with zeros.

int j = 0;
for(int i=0;i<n;i++)
  if(arr[i] != 0)
    arr[j++] = arr[i];
while(j < n)
  arr[j++] = 0;

- **Time:** $O(n)$, **Space:** $O(1)$.

(b) First Non-Repeating Element:
Find the first element that occurs exactly once.

Hashing Approach:

1. Traverse the array and store frequency of each element in a hash map.
2. Traverse again; the first element with frequency 1 is the answer.

unordered_map<int,int> freq;
for(int x : arr) freq[x]++;
for(int x : arr)
  if(freq[x] == 1) return x; // first non-repeating
return -1; // none found

- **Time:** $O(n)$, **Space:** $O(n)$.

Both solutions use a single/double pass, making them efficient and practical for competitive coding.