TCS NQT Coding Practice Guide — Java

Topic-wise problems, Arrays through Dynamic Programming

Important note before you start

TCS does not publish an official archive of past NQT coding questions, and exact questions are not reused year to year. What's consistent
across reported drives (2021–2026) is the pattern: array/string manipulation, basic data structures, and a DP problem for higher (Digital/
Prime) tracks. This guide gives you 4–5 representative problems per topic, written at the difficulty and style TCS NQT actually tests —
clean, interview-style Java, no unnecessary abstraction. Treat these as targeted practice, not leaked exam questions.
How TCS NQT coding usually grades: correctness on visible + hidden test cases, plus partial credit for edge cases (empty input, single
element, negative numbers, duplicates). Always handle those explicitly.

Page 1 of 27
 1. ARRAYS

1.1 Second Largest Element in an Array

Problem: Given an array of integers, find the second largest distinct element without sorting.

import [Link];

public class SecondLargest {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = [Link]();

int first = Integer.MIN_VALUE, second = Integer.MIN_VALUE;

for (int x : arr) {
if (x > first) {
second = first;
first = x;
} else if (x > second && x != first) {
second = x;
}
}
[Link](second == Integer.MIN_VALUE ? "No second largest" : second);
}
}

Complexity: O(n) time, O(1) space.

1.2 Move Zeros to End (Chocolate Packet style)

Problem: Given an array, push all 0s to the end while keeping the relative order of non-zero elements.

import [Link];

public class MoveZeros {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = [Link]();

int j = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
j++;
}
}
StringBuilder sb = new StringBuilder();
for (int x : arr) [Link](x).append(" ");
[Link]([Link]().trim());
}
}

Complexity: O(n) time, O(1) space (in-place, stable).

1.3 Find All Duplicates in an Array

Problem: Given an array of integers (1 to n range or general), print all elements that occur more than once.

Page 2 of 27
 import [Link].*;

public class FindDuplicates {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = [Link]();

Map<Integer, Integer> count = new HashMap<>();

for (int x : arr) [Link](x, [Link](x, 0) + 1);

List<Integer> duplicates = new ArrayList<>();

for ([Link]<Integer, Integer> e : [Link]()) {
if ([Link]() > 1) [Link]([Link]());
}
[Link](duplicates);
[Link]([Link]() ? "No duplicates" : duplicates);
}
}

Complexity: O(n) time, O(n) space.

1.4 Maximum Subarray Sum (Kadane's Algorithm)

Problem: Find the contiguous subarray with the largest sum.

import [Link];

public class MaxSubarraySum {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = [Link]();

int maxSoFar = arr[0], maxEndingHere = arr[0];

for (int i = 1; i < n; i++) {
maxEndingHere = [Link](arr[i], maxEndingHere + arr[i]);
maxSoFar = [Link](maxSoFar, maxEndingHere);
}
[Link](maxSoFar);
}
}

Complexity: O(n) time, O(1) space.

1.5 Rotate Array by K Positions

Problem: Rotate an array to the right by k steps, in place.

Page 3 of 27
 import [Link];

public class RotateArray {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = [Link]();
int k = [Link]() % n;

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

StringBuilder sb = new StringBuilder();

for (int x : arr) [Link](x).append(" ");
[Link]([Link]().trim());
}

static void reverse(int[] arr, int start, int end) {

while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
}

Complexity: O(n) time, O(1) space.

Page 4 of 27
 2. STRINGS

2.1 Reverse Words in a Sentence

Problem: Given a sentence, reverse the order of words (not the characters within each word).

import [Link];

public class ReverseWords {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String line = [Link]();
String[] words = [Link]().split("\\s+");

StringBuilder sb = new StringBuilder();

for (int i = [Link] - 1; i >= 0; i--) {
[Link](words[i]);
if (i != 0) [Link](" ");
}
[Link]([Link]());
}
}

Complexity: O(n) time, O(n) space.

2.2 Check if a String is a Palindrome (ignoring case and spaces)

Problem: Given a string, determine if it reads the same forward and backward, ignoring spaces and case.

import [Link];

public class PalindromeCheck {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String input = [Link]();
String cleaned = [Link]().replaceAll("[^a-z0-9]", "");

int left = 0, right = [Link]() - 1;

boolean isPalindrome = true;
while (left < right) {
if ([Link](left) != [Link](right)) {
isPalindrome = false;
break;
}
left++;
right--;
}
[Link](isPalindrome ? "Palindrome" : "Not a Palindrome");
}
}

Complexity: O(n) time, O(n) space.

2.3 First Non-Repeating Character

Problem: Find the first character in a string that does not repeat.

Page 5 of 27
 import [Link].*;

public class FirstNonRepeating {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String s = [Link]();

Map<Character, Integer> freq = new LinkedHashMap<>();

for (char c : [Link]()) {
[Link](c, [Link](c, 0) + 1);
}
char result = '\0';
for ([Link]<Character, Integer> e : [Link]()) {
if ([Link]() == 1) {
result = [Link]();
break;
}
}
[Link](result == '\0' ? "None" : result);
}
}

Complexity: O(n) time, O(n) space.

2.4 Check if Two Strings are Anagrams

Problem: Determine whether two given strings are anagrams of each other.

import [Link];
import [Link];

public class AnagramCheck {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String s1 = [Link]().replaceAll("\\s", "").toLowerCase();
String s2 = [Link]().replaceAll("\\s", "").toLowerCase();

if ([Link]() != [Link]()) {
[Link]("Not Anagrams");
return;
}
char[] a1 = [Link]();
char[] a2 = [Link]();
[Link](a1);
[Link](a2);
[Link]([Link](a1, a2) ? "Anagrams" : "Not Anagrams");
}
}

Complexity: O(n log n) time, O(n) space.

2.5 Count Occurrences of Each Character (String Compression style)

Problem: Compress a string by replacing consecutive repeated characters with the character followed by its count.

Page 6 of 27
 import [Link];

public class StringCompression {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String s = [Link]();
if ([Link]()) {
[Link]("");
return;
}

StringBuilder sb = new StringBuilder();

int count = 1;
for (int i = 1; i <= [Link](); i++) {
if (i < [Link]() && [Link](i) == [Link](i - 1)) {
count++;
} else {
[Link]([Link](i - 1));
if (count > 1) [Link](count);
count = 1;
}
}
[Link]([Link]());
}
}

Complexity: O(n) time, O(n) space.

Page 7 of 27
 3. LINKED LISTS

3.1 Reverse a Singly Linked List

Problem: Reverse a linked list in place.

import [Link];

public class ReverseLinkedList {

static class Node {
int data;
Node next;
Node(int data) { [Link] = data; }
}

static Node reverse(Node head) {

Node prev = null, curr = head;
while (curr != null) {
Node nextNode = [Link];
[Link] = prev;
prev = curr;
curr = nextNode;
}
return prev;
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
int n = [Link]();
Node head = null, tail = null;
for (int i = 0; i < n; i++) {
Node node = new Node([Link]());
if (head == null) head = tail = node;
else { [Link] = node; tail = node; }
}

head = reverse(head);
StringBuilder sb = new StringBuilder();
while (head != null) {
[Link]([Link]).append(" ");
head = [Link];
}
[Link]([Link]().trim());
}
}

Complexity: O(n) time, O(1) space.

3.2 Detect a Cycle in a Linked List

Problem: Determine if a linked list has a cycle using Floyd's cycle detection (slow/fast pointers).

Page 8 of 27
 public class DetectCycle {
static class Node {
int data;
Node next;
Node(int data) { [Link] = data; }
}

static boolean hasCycle(Node head) {

Node slow = head, fast = head;
while (fast != null && [Link] != null) {
slow = [Link];
fast = [Link];
if (slow == fast) return true;
}
return false;
}

public static void main(String[] args) {

Node head = new Node(1);
[Link] = new Node(2);
[Link] = new Node(3);
[Link] = head; // creates a cycle for testing

[Link](hasCycle(head) ? "Cycle Found" : "No Cycle");

}
}

Complexity: O(n) time, O(1) space.

3.3 Find the Middle Element of a Linked List

Problem: Find the middle node in a single pass.

import [Link];

public class MiddleOfList {

static class Node {
int data;
Node next;
Node(int data) { [Link] = data; }
}

static Node findMiddle(Node head) {

Node slow = head, fast = head;
while (fast != null && [Link] != null) {
slow = [Link];
fast = [Link];
}
return slow;
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
int n = [Link]();
Node head = null, tail = null;
for (int i = 0; i < n; i++) {
Node node = new Node([Link]());
if (head == null) head = tail = node;
else { [Link] = node; tail = node; }
}
[Link](findMiddle(head).data);
}
}

Complexity: O(n) time, O(1) space.

3.4 Remove Duplicates from a Sorted Linked List

Problem: Given a sorted linked list, remove duplicate nodes leaving only distinct values.

Page 9 of 27
 import [Link];

public class RemoveDuplicates {

static class Node {
int data;
Node next;
Node(int data) { [Link] = data; }
}

static Node removeDuplicates(Node head) {

Node curr = head;
while (curr != null && [Link] != null) {
if ([Link] == [Link]) {
[Link] = [Link];
} else {
curr = [Link];
}
}
return head;
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
int n = [Link]();
Node head = null, tail = null;
for (int i = 0; i < n; i++) {
Node node = new Node([Link]());
if (head == null) head = tail = node;
else { [Link] = node; tail = node; }
}

head = removeDuplicates(head);
StringBuilder sb = new StringBuilder();
while (head != null) {
[Link]([Link]).append(" ");
head = [Link];
}
[Link]([Link]().trim());
}
}

Complexity: O(n) time, O(1) space.

3.5 Merge Two Sorted Linked Lists

Problem: Merge two sorted linked lists into a single sorted linked list.

Page 10 of 27
 import [Link];

public class MergeSortedLists {

static class Node {
int data;
Node next;
Node(int data) { [Link] = data; }
}

static Node merge(Node l1, Node l2) {

if (l1 == null) return l2;
if (l2 == null) return l1;

Node dummy = new Node(0);

Node curr = dummy;
while (l1 != null && l2 != null) {
if ([Link] <= [Link]) {
[Link] = l1;
l1 = [Link];
} else {
[Link] = l2;
l2 = [Link];
}
curr = [Link];
}
[Link] = (l1 != null) ? l1 : l2;
return [Link];
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
int n1 = [Link]();
Node h1 = null, t1 = null;
for (int i = 0; i < n1; i++) {
Node node = new Node([Link]());
if (h1 == null) h1 = t1 = node;
else { [Link] = node; t1 = node; }
}
int n2 = [Link]();
Node h2 = null, t2 = null;
for (int i = 0; i < n2; i++) {
Node node = new Node([Link]());
if (h2 == null) h2 = t2 = node;
else { [Link] = node; t2 = node; }
}

Node merged = merge(h1, h2);

StringBuilder sb = new StringBuilder();
while (merged != null) {
[Link]([Link]).append(" ");
merged = [Link];
}
[Link]([Link]().trim());
}
}

Complexity: O(n + m) time, O(1) extra space.

Page 11 of 27
 4. STACKS AND QUEUES

4.1 Valid Parentheses (Balanced Brackets)

Problem: Given a string of brackets ()[]{} , determine if they are balanced.

import [Link];
import [Link];

public class ValidParentheses {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String s = [Link]();

Stack<Character> stack = new Stack<>();

boolean valid = true;
for (char c : [Link]()) {
if (c == '(' || c == '{' || c == '[') {
[Link](c);
} else if (c == ')' || c == '}' || c == ']') {
if ([Link]()) { valid = false; break; }
char top = [Link]();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '[')) {
valid = false;
break;
}
}
}
if (![Link]()) valid = false;
[Link](valid ? "Balanced" : "Not Balanced");
}
}

Complexity: O(n) time, O(n) space.

4.2 Implement a Stack Using an Array (with overflow/underflow checks)

Problem: Implement push, pop, and peek operations for a fixed-size stack.

Page 12 of 27
 import [Link];

public class ArrayStack {

int[] arr;
int top;
int capacity;

ArrayStack(int size) {
arr = new int[size];
capacity = size;
top = -1;
}

void push(int x) {
if (top == capacity - 1) {
[Link]("Stack Overflow");
return;
}
arr[++top] = x;
}

int pop() {
if (top == -1) {
[Link]("Stack Underflow");
return -1;
}
return arr[top--];
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
ArrayStack stack = new ArrayStack(5);
[Link](10);
[Link](20);
[Link](30);
[Link]("Popped: " + [Link]());
[Link]("Popped: " + [Link]());
}
}

Complexity: O(1) per operation.

4.3 Implement a Queue Using Two Stacks

Problem: Implement enqueue and dequeue operations using only two stacks.

Page 13 of 27
 import [Link];

public class QueueUsingStacks {

Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();

void enqueue(int x) {
[Link](x);
}

int dequeue() {
if ([Link]()) {
while (![Link]()) {
[Link]([Link]());
}
}
if ([Link]()) {
[Link]("Queue is empty");
return -1;
}
return [Link]();
}

public static void main(String[] args) {

QueueUsingStacks q = new QueueUsingStacks();
[Link](1);
[Link](2);
[Link](3);
[Link]([Link]());
[Link]([Link]());
}
}

Complexity: O(1) amortized for dequeue, O(1) for enqueue.

4.4 Next Greater Element (Monotonic Stack)

Problem: For each element in an array, find the next greater element to its right. If none exists, output -1.

import [Link];
import [Link];

public class NextGreaterElement {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = [Link]();

int[] result = new int[n];

Stack<Integer> stack = new Stack<>(); // stores indices

for (int i = n - 1; i >= 0; i--) {

while (![Link]() && arr[[Link]()] <= arr[i]) {
[Link]();
}
result[i] = [Link]() ? -1 : arr[[Link]()];
[Link](i);
}

StringBuilder sb = new StringBuilder();

for (int x : result) [Link](x).append(" ");
[Link]([Link]().trim());
}
}

Complexity: O(n) time, O(n) space.

Page 14 of 27
4.5 Evaluate a Postfix Expression
Problem: Evaluate a postfix (Reverse Polish) expression given as a space-separated string.

import [Link];
import [Link];

public class PostfixEvaluation {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String[] tokens = [Link]().trim().split("\\s+");

Stack<Integer> stack = new Stack<>();

for (String token : tokens) {
if ([Link]("-?\\d+")) {
[Link]([Link](token));
} else {
int b = [Link]();
int a = [Link]();
switch (token) {
case "+": [Link](a + b); break;
case "-": [Link](a - b); break;
case "*": [Link](a * b); break;
case "/": [Link](a / b); break;
}
}
}
[Link]([Link]());
}
}

Complexity: O(n) time, O(n) space.

Page 15 of 27
 5. TREES

5.1 Inorder, Preorder, Postorder Traversal of a Binary Tree

Problem: Implement all three depth-first traversals of a binary tree.

public class TreeTraversals {

static class Node {
int data;
Node left, right;
Node(int data) { [Link] = data; }
}

static void inorder(Node root, StringBuilder sb) {

if (root == null) return;
inorder([Link], sb);
[Link]([Link]).append(" ");
inorder([Link], sb);
}

static void preorder(Node root, StringBuilder sb) {

if (root == null) return;
[Link]([Link]).append(" ");
preorder([Link], sb);
preorder([Link], sb);
}

static void postorder(Node root, StringBuilder sb) {

if (root == null) return;
postorder([Link], sb);
postorder([Link], sb);
[Link]([Link]).append(" ");
}

public static void main(String[] args) {

Node root = new Node(1);
[Link] = new Node(2);
[Link] = new Node(3);
[Link] = new Node(4);
[Link] = new Node(5);

StringBuilder in = new StringBuilder(), pre = new StringBuilder(), post = new StringBuilder();

inorder(root, in);
preorder(root, pre);
postorder(root, post);

[Link]("Inorder: " + [Link]().trim());

[Link]("Preorder: " + [Link]().trim());
[Link]("Postorder: " + [Link]().trim());
}
}

Complexity: O(n) time, O(h) space (h = height, recursion stack).

5.2 Find the Height (Maximum Depth) of a Binary Tree

Problem: Return the number of nodes on the longest path from root to a leaf.

Page 16 of 27
 public class TreeHeight {
static class Node {
int data;
Node left, right;
Node(int data) { [Link] = data; }
}

static int height(Node root) {

if (root == null) return 0;
return 1 + [Link](height([Link]), height([Link]));
}

public static void main(String[] args) {

Node root = new Node(1);
[Link] = new Node(2);
[Link] = new Node(3);
[Link] = new Node(4);

[Link](height(root));
}
}

Complexity: O(n) time, O(h) space.

5.3 Level Order Traversal (BFS) of a Binary Tree

Problem: Print the tree level by level, left to right.

import [Link];
import [Link];

public class LevelOrderTraversal {

static class Node {
int data;
Node left, right;
Node(int data) { [Link] = data; }
}

static void levelOrder(Node root) {

if (root == null) return;
Queue<Node> queue = new LinkedList<>();
[Link](root);

while (![Link]()) {
int size = [Link]();
for (int i = 0; i < size; i++) {
Node curr = [Link]();
[Link]([Link] + " ");
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
[Link]();
}
}

public static void main(String[] args) {

Node root = new Node(1);
[Link] = new Node(2);
[Link] = new Node(3);
[Link] = new Node(4);
[Link] = new Node(5);

levelOrder(root);
}
}

Complexity: O(n) time, O(n) space (queue holds up to one level at a time).

Page 17 of 27
5.4 Check if a Binary Tree is a Valid BST
Problem: Determine whether a given binary tree satisfies the Binary Search Tree property.

public class ValidateBST {

static class Node {
int data;
Node left, right;
Node(int data) { [Link] = data; }
}

static boolean isValidBST(Node root, Long min, Long max) {

if (root == null) return true;
if ([Link] <= min || [Link] >= max) return false;
return isValidBST([Link], min, (long) [Link]) &&
isValidBST([Link], (long) [Link], max);
}

public static void main(String[] args) {

Node root = new Node(5);
[Link] = new Node(3);
[Link] = new Node(8);
[Link] = new Node(1);
[Link] = new Node(4);

boolean result = isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);

[Link](result ? "Valid BST" : "Not a Valid BST");
}
}

Complexity: O(n) time, O(h) space.

5.5 Lowest Common Ancestor (LCA) in a Binary Tree

Problem: Find the lowest common ancestor of two given nodes in a binary tree.

public class LowestCommonAncestor {

static class Node {
int data;
Node left, right;
Node(int data) { [Link] = data; }
}

static Node lca(Node root, int n1, int n2) {

if (root == null) return null;
if ([Link] == n1 || [Link] == n2) return root;

Node leftLCA = lca([Link], n1, n2);

Node rightLCA = lca([Link], n1, n2);

if (leftLCA != null && rightLCA != null) return root;

return (leftLCA != null) ? leftLCA : rightLCA;
}

public static void main(String[] args) {

Node root = new Node(1);
[Link] = new Node(2);
[Link] = new Node(3);
[Link] = new Node(4);
[Link] = new Node(5);

Node result = lca(root, 4, 5);

[Link]("LCA: " + [Link]);
}
}

Complexity: O(n) time, O(h) space.

Page 18 of 27
 6. GRAPHS

6.1 Breadth-First Search (BFS) Traversal

Problem: Given an adjacency list, perform BFS starting from a given node.

import [Link].*;

public class GraphBFS {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link](); // number of vertices
int e = [Link](); // number of edges

List<List<Integer>> adj = new ArrayList<>();

for (int i = 0; i < n; i++) [Link](new ArrayList<>());

for (int i = 0; i < e; i++) {

int u = [Link](), v = [Link]();
[Link](u).add(v);
[Link](v).add(u);
}
int start = [Link]();

boolean[] visited = new boolean[n];

Queue<Integer> queue = new LinkedList<>();
[Link](start);
visited[start] = true;

StringBuilder sb = new StringBuilder();

while (![Link]()) {
int curr = [Link]();
[Link](curr).append(" ");
for (int neighbor : [Link](curr)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
[Link](neighbor);
}
}
}
[Link]([Link]().trim());
}
}

Complexity: O(V + E) time, O(V) space.

6.2 Depth-First Search (DFS) Traversal

Problem: Given an adjacency list, perform DFS starting from a given node.

Page 19 of 27
 import [Link].*;

public class GraphDFS {

static void dfs(int node, List<List<Integer>> adj, boolean[] visited, StringBuilder sb) {
visited[node] = true;
[Link](node).append(" ");
for (int neighbor : [Link](node)) {
if (!visited[neighbor]) {
dfs(neighbor, adj, visited, sb);
}
}
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
int n = [Link]();
int e = [Link]();

List<List<Integer>> adj = new ArrayList<>();

for (int i = 0; i < n; i++) [Link](new ArrayList<>());

for (int i = 0; i < e; i++) {

int u = [Link](), v = [Link]();
[Link](u).add(v);
[Link](v).add(u);
}
int start = [Link]();

boolean[] visited = new boolean[n];

StringBuilder sb = new StringBuilder();
dfs(start, adj, visited, sb);
[Link]([Link]().trim());
}
}

Complexity: O(V + E) time, O(V) space.

6.3 Detect a Cycle in an Undirected Graph

Problem: Determine whether an undirected graph contains a cycle.

Page 20 of 27
 import [Link].*;

public class DetectCycleGraph {

static boolean dfs(int node, int parent, List<List<Integer>> adj, boolean[] visited) {
visited[node] = true;
for (int neighbor : [Link](node)) {
if (!visited[neighbor]) {
if (dfs(neighbor, node, adj, visited)) return true;
} else if (neighbor != parent) {
return true;
}
}
return false;
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
int n = [Link]();
int e = [Link]();

List<List<Integer>> adj = new ArrayList<>();

for (int i = 0; i < n; i++) [Link](new ArrayList<>());

for (int i = 0; i < e; i++) {

int u = [Link](), v = [Link]();
[Link](u).add(v);
[Link](v).add(u);
}

boolean[] visited = new boolean[n];

boolean hasCycle = false;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
if (dfs(i, -1, adj, visited)) {
hasCycle = true;
break;
}
}
}
[Link](hasCycle ? "Cycle Found" : "No Cycle");
}
}

Complexity: O(V + E) time, O(V) space.

6.4 Count Connected Components in a Graph

Problem: Count the number of disconnected components in an undirected graph.

Page 21 of 27
 import [Link].*;

public class ConnectedComponents {

static void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
visited[node] = true;
for (int neighbor : [Link](node)) {
if (!visited[neighbor]) dfs(neighbor, adj, visited);
}
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
int n = [Link]();
int e = [Link]();

List<List<Integer>> adj = new ArrayList<>();

for (int i = 0; i < n; i++) [Link](new ArrayList<>());

for (int i = 0; i < e; i++) {

int u = [Link](), v = [Link]();
[Link](u).add(v);
[Link](v).add(u);
}

boolean[] visited = new boolean[n];

int components = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, adj, visited);
components++;
}
}
[Link](components);
}
}

Complexity: O(V + E) time, O(V) space.

6.5 Shortest Path in an Unweighted Graph (BFS)

Problem: Find the shortest distance from a source node to all other nodes in an unweighted graph.

Page 22 of 27
 import [Link].*;

public class ShortestPathBFS {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int e = [Link]();

List<List<Integer>> adj = new ArrayList<>();

for (int i = 0; i < n; i++) [Link](new ArrayList<>());

for (int i = 0; i < e; i++) {

int u = [Link](), v = [Link]();
[Link](u).add(v);
[Link](v).add(u);
}
int source = [Link]();

int[] dist = new int[n];

[Link](dist, -1);
dist[source] = 0;

Queue<Integer> queue = new LinkedList<>();

[Link](source);

while (![Link]()) {
int curr = [Link]();
for (int neighbor : [Link](curr)) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[curr] + 1;
[Link](neighbor);
}
}
}

for (int i = 0; i < n; i++) {

[Link]("Node " + i + ": " + dist[i]);
}
}
}

Complexity: O(V + E) time, O(V) space.

Page 23 of 27
 7. DYNAMIC PROGRAMMING

Per candidate reports across recent drives, DP is the strongest differentiator for the TCS Digital/Prime tracks — it shows up far more often
there than in the basic Ninja-level slot. Master the recurrence relation for each before looking at the code.

7.1 Fibonacci Number (Memoization vs Tabulation)

Problem: Compute the nth Fibonacci number efficiently.

import [Link];

public class Fibonacci {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();

if (n <= 1) {
[Link](n);
return;
}
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
[Link](dp[n]);
}
}

Recurrence: dp[i] = dp[i-1] + dp[i-2] Complexity: O(n) time, O(n) space (can be optimized to O(1) with two variables).

7.2 0/1 Knapsack Problem

Problem: Given weights and values of n items and a knapsack of capacity W, find the maximum value that can be put in the knapsack
(each item used at most once).

import [Link];

public class Knapsack01 {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] weight = new int[n];
int[] value = new int[n];
for (int i = 0; i < n; i++) weight[i] = [Link]();
for (int i = 0; i < n; i++) value[i] = [Link]();
int W = [Link]();

int[][] dp = new int[n + 1][W + 1];

for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (weight[i - 1] <= w) {
dp[i][w] = [Link](value[i - 1] + dp[i - 1][w - weight[i - 1]], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
[Link](dp[n][W]);
}
}

Page 24 of 27
Recurrence: dp[i][w] = max(dp[i-1][w], value[i-1] + dp[i-1][w-weight[i-1]]) if item fits, else dp[i-1][w] Complexity:
O(n × W) time, O(n × W) space.

7.3 Longest Common Subsequence (LCS)

Problem: Given two strings, find the length of their longest common subsequence.

import [Link];

public class LongestCommonSubsequence {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String s1 = [Link]();
String s2 = [Link]();

int m = [Link](), n = [Link]();

int[][] dp = new int[m + 1][n + 1];

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {
if ([Link](i - 1) == [Link](j - 1)) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = [Link](dp[i - 1][j], dp[i][j - 1]);
}
}
}
[Link](dp[m][n]);
}
}

Recurrence: dp[i][j] = 1 + dp[i-1][j-1] if chars match, else max(dp[i-1][j], dp[i][j-1]) Complexity: O(m × n) time, O(m
× n) space.

7.4 Coin Change (Minimum Coins / Number of Ways)

Problem: Given coin denominations and a target amount, find the minimum number of coins needed to make that amount (or -1 if
impossible).

import [Link];
import [Link];

public class CoinChange {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] coins = new int[n];
for (int i = 0; i < n; i++) coins[i] = [Link]();
int amount = [Link]();

int[] dp = new int[amount + 1];

[Link](dp, amount + 1); // initialize to "infinity"
dp[0] = 0;

for (int i = 1; i <= amount; i++) {

for (int coin : coins) {
if (coin <= i) {
dp[i] = [Link](dp[i], dp[i - coin] + 1);
}
}
}
[Link](dp[amount] > amount ? -1 : dp[amount]);
}
}

Recurrence: dp[i] = min(dp[i], dp[i-coin] + 1) for each coin ≤ i Complexity: O(amount × coins) time, O(amount) space.

Page 25 of 27
7.5 Longest Increasing Subsequence (LIS)
Problem: Find the length of the longest strictly increasing subsequence in an array.

import [Link];

public class LongestIncreasingSubsequence {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = [Link]();

int[] dp = new int[n];

[Link](dp, 1); // every element is an LIS of length 1 by itself

int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = [Link](dp[i], dp[j] + 1);
}
}
maxLen = [Link](maxLen, dp[i]);
}
[Link](maxLen);
}
}

Recurrence: dp[i] = max(dp[i], dp[j] + 1) for all j < i where arr[j] < arr[i] Complexity: O(n²) time, O(n) space. (Can be
optimized to O(n log n) with binary search.)

7.6 Minimum Path Sum in a Grid

Problem: Given a grid of non-negative numbers, find a path from top-left to bottom-right that minimizes the sum, moving only right or
down.

import [Link];

public class MinPathSum {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int rows = [Link]();
int cols = [Link]();
int[][] grid = new int[rows][cols];
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
grid[i][j] = [Link]();

int[][] dp = new int[rows][cols];

dp[0][0] = grid[0][0];

for (int i = 1; i < rows; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];

for (int j = 1; j < cols; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];

for (int i = 1; i < rows; i++) {

for (int j = 1; j < cols; j++) {
dp[i][j] = grid[i][j] + [Link](dp[i - 1][j], dp[i][j - 1]);
}
}
[Link](dp[rows - 1][cols - 1]);
}
}

Recurrence: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) Complexity: O(rows × cols) time, O(rows × cols) space.

Page 26 of 27
 Quick Revision Table

Topic Key Pattern Recommended Order to Revise

Arrays Two-pointer, Kadane's, in-place swap 1st

Strings Frequency map, two-pointer 2nd

Linked List Fast/slow pointer, dummy node 3rd

Stack/Queue Monotonic stack, two-stack trick 4th

Trees DFS recursion, BFS with queue 5th

Graphs Adjacency list + visited array 6th

DP Identify recurrence, then code bottom-up 7th (most time, highest payoff for Digital/Prime)

Final tip: TCS NQT's online judge scores partial credit for edge cases. Before submitting any solution, mentally test: empty input, single
element, all-same elements, and (for arrays/strings) negative numbers.

Page 27 of 27