Topic: 1.

Arrays & Searching

Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

1. Peak Element in an Array

Problem Statement:
A peak element in an array is an element that is greater than its neighbors. You are given a 0-indexed
integer array nums, where:
• nums[i] is a peak if nums[i] > nums[i-1] (previous element) and nums[i] > nums[i+1] (next element).
• Assume virtual boundary conditions, meaning nums[-1] = nums[n] = -∞ (negative infinity).
• If multiple peaks exist, return any one of them.
Your task is to find a peak element and return its index.
Input Format:
• An integer array nums, representing the list of elements.
Output Format:
• An integer representing the index of any peak element in nums.
Example Cases:
Example 1:
Input: nums = [1, 2, 3, 1]
Output: 2
Explanation:
- `nums[2] = 3` is a peak since `3 > 2` (left) and `3 > 1` (right).
Example 2:
Input: nums = [1, 2, 1, 3, 5, 6, 4]
Output: 5
Explanation:
- `nums[5] = 6` is a peak since `6 > 5` (left) and `6 > 4` (right).
Example 3:
Input: nums = [10, 20, 15, 2, 23, 90, 67]
Output: 1
Explanation:
- `nums[1] = 20` is a peak since `20 > 10` (left) and `20 > 15` (right).
Constraints:
• 1 ≤ [Link] ≤ 1000
• -2^31 ≤ nums[i] ≤ 2^31 - 1
• nums[i] != nums[i + 1] (no consecutive equal elements)

2. Problem Title: Maximum Product Subarray

Problem Statement:
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the
largest product, and return that product.
You must consider both positive and negative numbers, as the product of two negative numbers can
become positive. Also, be mindful of zero, which resets any product.
Input:
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

• An integer array nums of length n where

1 <= [Link] <= 20,000
-10 <= nums[i] <= 10
Output:
• An integer representing the maximum product of a contiguous subarray.
Example 1:
Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: The subarray [2, 3] has the maximum product 6.
Example 2:
Input: nums = [-2, 0, -1]
Output: 0
Explanation: The result cannot be 2, because [-2, -1] is not a contiguous subarray (0 separates them).
Constraints:
• 1 <= [Link] <= 20,000
• -10 <= nums[i] <= 10

3. Problem Title: Maximum Sum Subarray (Kadane’s Algorithm)

Problem Statement:
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the
largest sum, and return that sum.
This problem is commonly solved using Kadane's Algorithm, which efficiently finds the maximum sum in
linear time.
Input:
• An integer array nums of length n where
1 <= [Link] <= 100,000
-10⁴ <= nums[i] <= 10⁴
Output:
• An integer representing the maximum sum of a contiguous subarray.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The array itself is the subarray with the maximum sum.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The entire array has the largest sum.
Constraints:
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

• 1 <= [Link] <= 100,000

• -10⁴ <= nums[i] <= 10⁴

4. Sliding Window Maximum

Problem Statement:
Given an array of integers nums and an integer k, return an array of the maximum value in each sliding
window of size k.
A sliding window is a contiguous subarray of length k that moves from left to right one element at a time.
Input Format:
• An integer n, the size of the array.
• An integer array nums of size n.
• An integer k, the size of the sliding window.
Output Format:
• An array of integers, where each element represents the maximum value of the corresponding sliding
window.
Example:
Input:
n=8
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k=3
Output:
[3, 3, 5, 5, 6, 7]
Explanation:
Each window contains the following values:
• [1, 3, -1] → Max: 3
• [3, -1, -3] → Max: 3
• [-1, -3, 5] → Max: 5
• [-3, 5, 3] → Max: 5
• [5, 3, 6] → Max: 6
• [3, 6, 7] → Max: 7
Thus, the final output is [3, 3, 5, 5, 6, 7].
Constraints:
• 1 ≤ n ≤ 100
• 1 ≤ nums[i] ≤ 10^4
• 1≤k≤n

5. Problem Title: Top K Frequent Elements

Problem Statement:
Given an array of integers nums of length N, return the k most frequent elements.
If multiple elements have the same frequency, prefer the larger number among them.
Return the result in decreasing order of frequency. If two elements have the same frequency, order them
by descending numerical value.
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Input:
• An integer N representing the size of the array.
• An array of integers nums of size N.
• An integer k representing how many top frequent elements to return.
Output:
• A list of k integers, representing the top k most frequent elements, in order of frequency and value as
per the rules.
Example:
Input:
N=6
nums = [1, 1, 1, 2, 2, 3]
k=2

Output:
12

Explanation:
- Frequency of 1 = 3
- Frequency of 2 = 2
- Frequency of 3 = 1

Top 2 frequent elements are 1 and 2.

Constraints:
• 1 ≤ N ≤ 25
• 1 ≤ nums[i] ≤ 100
• 1≤k≤4

6. Problem Title: Minimum Absolute Difference Partition

Problem Statement:
You are given an array of integers arr of length n. Your task is to partition the array into two non-empty parts
such that the absolute difference between the sum of the two parts is minimized.
The partition is done at an index i such that:
• The first part includes elements from index 0 to i (arr[0] to arr[i])
• The second part includes elements from index i + 1 to n - 1 (arr[i+1] to arr[n-1])
Your goal is to find the partition index i (where 0 ≤ i < n - 1) for which the absolute difference between the
sums of the two parts is minimized.
If there are multiple such indices, return the smallest index.
Input:
• An integer array arr of length n
2 ≤ n ≤ 100,000
-10⁴ ≤ arr[i] ≤ 10⁴
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Output:
• An integer representing the best partition index i that gives the minimum absolute difference
between the sum of the two parts.

Example:
Input:
arr = [1, 2, 3, 4, 5]

Output:
2

Explanation:
Total sum = 15

Try partitioning at different indices:

i = 0 → left = [1], right = [2,3,4,5] → diff = |1 - 14| = 13
i = 1 → left = [1,2], right = [3,4,5] → diff = |3 - 12| = 9
i = 2 → left = [1,2,3], right = [4,5] → diff = |6 - 9| = 3
i = 3 → left = [1,2,3,4], right = [5] → diff = |10 - 5| = 5

Minimum absolute difference = 3 at index 2 → Output: 2

Constraints:
• 2 ≤ [Link] ≤ 100,000
• -10⁴ ≤ arr[i] ≤ 10⁴

7. Problem Title: Lexicographically Smallest Array After One Swap

Problem Statement:
You are given an array A of N integers and an integer K. You are allowed to swap at most one pair of
elements (A[i], A[j]) such that the absolute difference of their indices is at most K, i.e., |i - j| ≤ K.
Your task is to perform at most one such swap in the array to make the array lexicographically smallest.
Return the array after the swap. If the array is already lexicographically smallest within the given constraints,
return it as-is.

Input:
• An integer N — the size of the array
• An array A of N integers
• An integer K — the maximum allowed index distance for the swap

Output:
• The modified array after performing at most one valid swap that yields the lexicographically smallest
result.
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Example:
Input:
N=5
A = [5, 4, 3, 2, 1]
K=3

Output:
2
4
3
5
1

Explanation:
- To make the array smallest lexicographically, look for the smallest possible element within a K-range.
- Swapping A[0] = 5 and A[3] = 2 (|0 - 3| = 3 ≤ K) gives [2, 4, 3, 5, 1], which is lexicographically smaller than any
other swap.

Constraints:
• 1 ≤ N ≤ 10⁵
• 1 ≤ A[i] ≤ 10⁹
• 1≤K≤N

8. Problem Title: Minimum Folds for Blanket

Problem Statement:
You are given the dimensions of a blanket and a box. Your task is to compute the minimum number of folds
required to make the blanket fit into the box.
• A fold operation can reduce either the height or the width of the blanket by half (rounded up if
needed).
• You can fold the blanket any number of times in either direction (height or width).
• The goal is to fold the blanket such that both its height and width are less than or equal to the box's
dimensions.
Return the minimum number of folds required to make the blanket fit inside the box.

Input:
• Four integers:
o H = Height of the blanket
o W = Width of the blanket
o H1 = Height of the box
o W1 = Width of the box
Output:
• An integer representing the minimum number of folds required.
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Example:
Input:
H = 2, W = 3
H1 = 2, W1 = 2

Output:
1

Explanation:
- The blanket is 2 x 3 and the box is 2 x 2.
- Only one fold needed: fold the width 3 to 2 (or less).

Constraints:
• 1 ≤ H, W, H1, W1 ≤ 10⁹

9. Problem Title: Heavier Half (Minimum Coins for Majority)

Problem Statement:
You are given an array arr of positive integers. Your task is to select the minimum number of largest
elements such that the sum of the selected elements is strictly greater than the sum of the remaining
elements.
Return the minimum number of elements required to achieve this.

Input:
• An integer array arr of length n
(1 ≤ n ≤ 10⁵, 1 ≤ arr[i] ≤ 10⁴)

Output:
• An integer — the minimum number of largest elements whose total sum is greater than the sum
of the rest.

Example:
Input:
arr = [2, 17, 7, 3]

Output:
1

Explanation:
- Total sum = 29
- Sorting in descending order: [17, 7, 3, 2]
- Take 17 → sum = 17, remaining = 12 → 17 > 12 → Done
- So, minimum elements needed = 1
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Constraints:
• 1 ≤ [Link] ≤ 10⁵
• 1 ≤ arr[i] ≤ 10⁴

10. Problem Title: Stock Span Problem

Problem Statement:
Design a class StockSpanner that calculates the stock span for each day. The stock span is defined as the
number of consecutive days (including today) the stock price was less than or equal to today’s price.
Implement the following method:
• next(price: int) -> int:
Receives the price of the stock for the current day and returns the span of that price.
You are given a sequence of method calls and their arguments as:
• A list of operations: ["StockSpanner", "next", "next", ...]
• A list of arguments: [[], [price1], [price2], ...]
Return a list of results corresponding to each operation. For the constructor, return null.

Input:
• A list of operations and a list of input values for those operations.
Output:
• A list where each element corresponds to the return value of the respective operation. Use null for
the constructor.

Example:
Input:
operations = ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
values = [[], [100], [80], [60], [70], [60], [75], [85]]

Output:
[null, 1, 1, 1, 2, 1, 4, 6]

Explanation:
- Day 1: price = 100 → no previous greater → span = 1
- Day 2: price = 80 → last price > 80 is 100 → span = 1
- Day 3: price = 60 → last price > 60 is 80 → span = 1
- Day 4: price = 70 → last price > 70 is 80 → [60,70] → span = 2
- Day 5: price = 60 → span = 1
- Day 6: price = 75 → [60,70,75] → span = 4
- Day 7: price = 85 → [60,70,75,85] → span = 6

Constraints:
• 1 <= price <= 10⁵
• At most 10⁴ calls to next will be made.
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

11. Problem Title: Inversion Count in an Array

Problem Statement:
Given an array of integers, your task is to count the number of inversions in the array.
An inversion is a pair of indices (i, j) such that:
• i < j, and
• arr[i] > arr[j]
In other words, it's a pair where a larger element appears before a smaller one in the array.
Your goal is to compute the total number of such inversions in the array.

Input Format:
• First line contains a single integer N — the size of the array.
• Second line contains N space-separated integers — the elements of the array arr.

Output Format:
• Print a single integer — the total number of inversions in the array.

Constraints:
• 1 ≤ N ≤ 5 × 10⁵
• 1 ≤ arr[i] ≤ 10¹⁸

Sample Input:
5
24135
Sample Output:
3
Explanation:
The 3 inversions are:
• (0, 2) → 2 > 1
• (1, 2) → 4 > 1
• (1, 3) → 4 > 3

12. Problem Title: K-th Permutation Sequence

Problem Statement:
You are given two integers n and k. Your task is to return the k-th permutation sequence of numbers from 1
to n when all permutations are arranged in lexicographic order.
You should generate the k-th permutation without generating all possible permutations.

Input Format:
• First line: Integer n — the range of numbers (from 1 to n)
• Second line: Integer k — the 1-based index of the desired permutation

Output Format:
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

• A string representing the k-th permutation in lexicographic order.

Constraints:
• 1≤n≤9
• 1 ≤ k ≤ n!

Sample Input:
3
3
Sample Output:
213

Explanation:
All permutations of [1, 2, 3] in lexicographic order are:
1. 123
2. 132
3. 213 ← this is the 3rd permutation
4. 231
5. 312
6. 321
So, the output is 213.

13. Problem Title: Minimum Exercises to Exhaust Energy

Problem Statement:
You are given an integer E representing your initial energy level and a list of N exercises. Each exercise has
an associated energy drain given by an array A of N integers, where A[i] is the amount of energy reduced by
the i-th exercise.
You may choose to perform any exercise at most two times. Your goal is to reduce your energy to 0 or
below, using the minimum number of total exercises.
If it is not possible to reduce the energy to 0 or below using the available exercises (each at most twice),
output -1.

Input Format:
• First line: An integer E — initial energy.
• Second line: An integer N — number of exercises.
• Next N lines: Each line contains one integer A[i] — energy drain of the i-th exercise.

Output Format:
• A single integer — the minimum number of exercises needed to exhaust the energy, or -1 if it's not
possible.
Constraints:
• 1 < E < 10⁵
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

• 1 < N < 10⁵

• 1 < A[i] < 10⁵

Sample Input:
6
2
1
2
Sample Output:
4

Explanation:
• You can perform:
o Exercise 1 (energy = 1) two times → total = 2
o Exercise 2 (energy = 2) two times → total = 4
o Total energy drained = 1 + 1 + 2 + 2 = 6
• Energy becomes 0 → Done in 4 exercises

14. Problem Title: Make Array a Mountain

Problem Statement:
You are given an array of integers. Your task is to modify the minimum number of elements to transform
the array into a mountain array.
A mountain array is defined as an array that:
• Strictly increases to a single peak, and then
• Strictly decreases after the peak.
More formally, for some index i (0 < i < N−1):
• arr[0] < arr[1] < ... < arr[i], and
• arr[i] > arr[i+1] > ... > arr[N−1]
Your goal is to convert the input array into such a mountain, with the minimum number of element
modifications (changes in value).
Return the minimum number of changes required.

Input Format:
• First line: An integer N — the number of elements in the array.
• Next N lines: Each line contains one integer, the i-th element of the array.

Output Format:
• A single integer — the minimum number of changes needed to convert the array into a mountain.

Constraints:
• 1 < N < 10⁵
• 1 < array[i] < 10⁶
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Sample Input:
6
3
3
4
4
5
5

Sample Output:
3

Explanation:
We can convert the array [3, 3, 4, 4, 5, 5] to a mountain like [3, 4, 5, 4, 3, 2] or [1, 2, 3, 4, 3, 2], but in this case,
the fewest changes result in a minimum of 3 modifications.

15. Problem Title: Kingdom of Numeria

Problem Statement:
In the Kingdom of Numeria, each village has a certain amount of wealth. You are given an array where each
element represents the wealth of a village.
Your task is to find the smallest possible maximum difference in wealth among any K contiguous
villages.
Formally, for every subarray of size K, compute the difference between the maximum and minimum wealth
in that subarray. Among all such differences, find and return the minimum.

Input Format:
• First line: Integer N — the number of villages.
• Second line: N space-separated integers — the wealth of the villages.
• Third line: Integer K — the size of the group of contiguous villages to consider.

Output Format:
• A single integer — the smallest possible maximum difference in wealth among all contiguous
subarrays of size K.

Constraints:
• 1 ≤ N ≤ 10⁵
• −10⁶ ≤ arr[i] ≤ 10⁶
• 1≤K≤N

Sample Input:
6
839165
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

3
Sample Output:
5

Explanation:
All contiguous subarrays of size 3 and their max-min differences:
• [8, 3, 9] → max = 9, min = 3 → diff = 6
• [3, 9, 1] → max = 9, min = 1 → diff = 8
• [9, 1, 6] → max = 9, min = 1 → diff = 8
• [1, 6, 5] → max = 6, min = 1 → diff = 5
Minimum of all differences = 5

16. Problem Title: Chef’s Energy Boost Plan

Problem Statement:
Chef is planning an energy boost by drinking smoothies for a continuous streak of days. Each smoothie gives
either a positive or negative amount of energy depending on its ingredients.
Chef wants to select a streak of exactly k consecutive days to get the maximum possible energy boost.
You are given the energy values of smoothies for n days (can be positive or negative). Your task is to find the
maximum total energy Chef can gain from any subarray of size k.

Input Format:
• First line: Two space-separated integers n and k — the number of days and the streak length.
• Second line: n space-separated integers — the energy values of the smoothies on each day.

Output Format:
• A single integer — the maximum total energy of any contiguous subarray of size k.

Constraints:
• 1 ≤ n ≤ 10⁵
• −10⁶ ≤ energy[i] ≤ 10⁶

Sample Input:
62
-1 -2 -3 4 5 6
Sample Output:
11

Explanation:
All subarrays of size 2:
• [-1, -2] → sum = -3
• [-2, -3] → sum = -5
• [-3, 4] → sum = 1
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

• [4, 5] → sum = 9
• [5, 6] → sum = 11 ← maximum
So, the answer is 11.

17. Problem Title: Matrix Sum of Distinct Regions

Problem Statement:
You are given an N × N matrix of integers and a central submatrix of size K × K.
Your task is to compute the total sum of three distinct non-overlapping regions of the matrix:
1. Main Diagonal and Adjacent Diagonals:
o Include the main diagonal (i = j)
o Include one diagonal to the left (i = j + 1) and one to the right (i = j − 1), if within bounds
2. Border Elements:
o All elements in the first and last rows
o All elements in the first and last columns
o Exclude any elements already counted in the diagonals or center
3. Central K × K Submatrix:
o The center square submatrix of size K×K
o Centered within the N×N matrix
o Exclude any overlapping elements that were already part of diagonals or borders
Return the sum of all elements in these three non-overlapping regions.

Input Format:
• First line: Two integers N and K
• Next N lines: Each line contains N space-separated integers — the matrix elements

Output Format:
• A single integer — the sum of elements from the three distinct regions

Constraints:
• 1 ≤ K ≤ N ≤ 100
• −10³ ≤ mat[i][j] ≤ 1

Sample Input:
53
11111
11111
11111
11111
11111

Sample Output:
39
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

18: Split Array into K Subarrays with Minimum Max Sum

Problem Statement:
You are given an array of n non-negative integers and a number k. You must split the array into k non-empty
contiguous subarrays such that the maximum sum among these subarrays is minimized.
Your goal is to determine the minimum possible maximum subarray sum achievable by such a split.

Input Format:
• First line: Two space-separated integers n and k
• Second line: n space-separated integers representing the array

Output Format:
• A single integer: the minimum possible maximum subarray sum

Constraints:
• 1 ≤ n ≤ 10⁴
• 1 ≤ array[i] ≤ 10⁵

Sample Input:
52
7 2 5 10 8
Sample Output:
18

Explanation:
Split the array as [7,2,5] and [10,8] → subarray sums: 14 and 18.
The maximum of these is 18, which is minimized.

19: Maximum Sum of Non-Overlapping Intervals

Problem Statement:
You are given n intervals. Each interval has a start time, end time, and a value. You can select non-
overlapping intervals such that their total value is maximized.
Your task is to choose a subset of non-overlapping intervals with the maximum total value.

Input Format:
• First line: Integer n — number of intervals
• Next n lines: Each line contains three integers: start, end, and value

Output Format:
• A single integer: Maximum total value of the selected non-overlapping intervals

Constraints:
• 1 ≤ n ≤ 10⁵
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

• 1 ≤ start < end ≤ 10⁹

• 0 ≤ value ≤ 10⁹

Sample Input:
4
1 3 50
3 5 20
6 19 100
2 100 200
Sample Output:
200

Explanation:
• Intervals [1,3] and [6,19] are non-overlapping → total = 150
• But interval [2,100] has value 200 → better to pick it alone

20: Minimum Swaps in Selection Sort

Problem Statement:
You are organizing a sorting contest where participants use selection sort. Your task is to compute the
minimum number of swaps required to sort a given array in strictly increasing order using the logic of
selection sort.
Remember, in each iteration, selection sort selects the minimum element from the unsorted portion and
swaps it with the first unsorted element.

Input Format:
• First line: Integer n — number of elements in the array
• Second line: n space-separated integers representing the array

Output Format:
• A single integer: Minimum number of swaps required
Constraints:
• 1 ≤ n ≤ 10
• 0 ≤ arr[i] ≤ 100

Example 1:
Input:
4
4321

Output:
2
Explanation:
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

• Swap 4 with 1 → [1,3,2,4]

• Swap 3 with 2 → [1,2,3,4]

Example 2:
Input:
5
10 19 6 3 5

Output:
2
Explanation:
• Swap 10 with 3 → [3,19,6,10,5]
• Swap 19 with 5 → [3,5,6,10,19]

21: Equalize Water Levels in Dams

Problem Statement:
You are given the heights of N mountain reservoirs: H1, H2, ..., Hn. Water can be released from a reservoir to
any lower level. The cost of lowering the water from a higher to a lower level is the difference in their heights.
Your goal is to equalize the heights of all reservoirs such that the total energy (cost) is minimized.

Input Format:
• First line: Integer n — number of reservoirs
• Second line: n space-separated integers H[0] H[1] ... H[n-1]

Output Format:
• A single integer: minimum total energy required to make all heights equal

Constraints:
• 1 ≤ n ≤ 10⁵
• 1 ≤ H[i] ≤ 10⁹

Examples:
Input:
4
8363
Output:
11
Explanation:
Reduce all to height 3: (8−3) + (6−3) = 5 + 3 = 8
3 and 3 need no change.

Input:
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

3
100 100 100
Output:
0

22: Fighter Killing with Power Thresholds

Problem Statement:
Ram fights in Q rounds. In each round, Ram has a certain power M. He can defeat all fighters whose power
is less than or equal to M.
Each round is independent, and defeated fighters revive for the next round.
For each round, you must print:
1. The number of fighters Ram defeats
2. The total power of defeated fighters

Input Format:
• First line: Integer n — number of fighters
• Second line: n space-separated integers — power of each fighter
• Third line: Integer q — number of rounds
• Next q lines: Each contains an integer M — Ram’s power in that round

Output Format:
• For each query, print two integers:
number_of_defeated_fighters total_power_of_defeated_fighters

Constraints:
• 1 ≤ n ≤ 10,000
• 1 ≤ fighter power ≤ 100
• 1 ≤ q ≤ 10,000
• 1 ≤ M ≤ 100

Example Input:
7
1234567
3
3
10
2
Example Output:
36
7 28
23
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

23: Maximum Subarray Sum (Kadane’s Algorithm)

Problem Statement:
Given an array of integers, find the contiguous subarray (containing at least one number) which has the
largest sum, and return that sum.

Input Format:
• First line: Integer n — size of array
• Second line: n space-separated integers — array elements

Output Format:
• A single integer — the maximum subarray sum

Constraints:
• 1 ≤ n ≤ 20
• −100 ≤ nums[i] ≤ 100

Sample Input:
5
5 4 -1 7 8
Sample Output:
23

24: Alternating Subsequence Maximum Sum

Problem Statement:
Given an array, your task is to find the maximum sum of an alternating subsequence starting with the first
element.
Alternating means: decrease → increase → decrease → ...
You can only pick elements that follow this pattern strictly in the given order.

Input Format:
• First line: Integer n — number of elements
• Second line: n space-separated integers

Output Format:
• A single integer — the maximum sum of a valid alternating subsequence
Constraints:
• 1 ≤ n ≤ 10
• 1 ≤ elements ≤ 100

Sample Input:
6
438538
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Sample Output:
28

25: Mountain Array Transformation

Problem Statement:
You are given an array A of N integers. Your goal is to transform it into a Mountain Array using the minimum
number of element changes.
A Mountain Array is defined as:
• Both ends have equal values
• From either end to the middle, values increase by 1
• The pattern must rise and fall symmetrically
Your task is to find the minimum number of elements to change to make the array a valid Mountain Array.

Input Format:
• First line: Integer N — size of the array
• Second line: N space-separated integers

Output Format:
• A single integer — minimum number of changes required

26: Stock Buy and Sell with at most K Transactions

Problem Statement:
You are given an array prices[] where prices[i] is the price of a stock on day i, and an integer k representing
the maximum number of allowed transactions.
You may complete at most k transactions. A transaction consists of buying and then selling one share of the
stock.
Your task is to find the maximum profit you can make under these conditions.

Input Format:
• First line: An array of integers prices[]
• Second line: Integer k

Output Format:
• A single integer: the maximum profit

Constraints:
• 1 ≤ [Link] ≤ 1000
• 1 ≤ k ≤ 200
• 1 ≤ prices[i] ≤ 1000

Sample Input:
prices = [10, 22, 5, 80]
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

k=2
Sample Output:
87

27: Sliding-Window Distinct Count

Problem Statement:
You are given an array A of length N and Q queries. Each query gives you a range (L, R) and asks how many
distinct elements exist in the subarray from index L to R (1-based indexing).

Input Format:
• First line: Two integers N and Q
• Second line: N space-separated integers
• Next Q lines: Each contains two integers L and R

Output Format:
• For each query, print the number of distinct elements in the subarray [L, R]

Constraints:
• 1 ≤ N, Q ≤ 2 × 10⁵
• 1 ≤ A[i] ≤ 10⁹
• 1≤L≤R≤N

Sample Input:
53
12132
15
24
33
Sample Output:
3
2
1

28: Intersection of Two Sorted Arrays

Problem Statement:
Given two sorted arrays A and B, find all elements that occur in both arrays, including duplicates (i.e., the
intersection must include correct multiplicity).

Input Format:
• Two lines, each containing space-separated integers of arrays A and B

Output Format:
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

• A line containing the intersection array with correct multiplicity

Constraints:
• 1 ≤ |A|, |B| ≤ 10⁶

Sample Input:
A = [1 2 3 3 4 5 6]
B = [3 3 5]
Sample Output:
335

29: Minimum Number of Towers

Problem Statement:
You are given a sequence of n cubes. You must build towers with the following rules:
• You can start a new tower, or
• You can place a cube on top of an existing tower only if the cube is smaller than the cube currently
on top of that tower.
Return the minimum number of towers required to place all cubes.

Input Format:
• First line: Integer n — number of cubes
• Second line: n space-separated integers — sizes of the cubes

Output Format:
• A single integer — minimum number of towers needed

Constraints:
• 1 ≤ n ≤ 10⁵

Sample Input:
5
38215
Sample Output:
2

30: Max Element in Array

Problem Statement:
Given an array of N integers, find and print the maximum element.

Input Format:
• First line: Integer N — number of elements
• Second line: N space-separated integers
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Output Format:
• A single integer — the maximum element

Constraints:
• 1 ≤ N ≤ 1000
• −10⁹ ≤ arr[i] ≤ 10⁹

Sample Input:
5
-2 -19 8 15 4
Sample Output:
15

31. Number Distribution

Problem Statement:
Given an array of integers, count how many numbers are positive, negative, and zeros.

Input Format:
• First line: Integer N, the number of elements in the array
• Second line: N space-separated integers

Output Format:
• Print three integers separated by a space:
o Number of zeros
o Number of positive integers
o Number of negative integers

Constraints:
• 1 ≤ N ≤ 10⁴
• −10³ ≤ arr[i] ≤ 10³

Sample Input:
10
120 0 -9 89 68 -982 91 -54 -12 -139
Sample Output:
145

32. Reverse Array (Recursion only)

Problem Statement:
Write a function to print the elements of an array in reverse order using recursion only (no loops allowed).
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Input Format:
• First line: Integer N, number of elements
• Second line: N space-separated integers

Output Format:
• Print the array in reverse order, space-separated

Constraints:
• 1 ≤ N ≤ 100
• 0 ≤ arr[i] ≤ 1000

Sample Input:
5
2 19 8 15 4
Sample Output:
4 15 8 19 2

33. Odd and Even Sum

Problem Statement:
Given an array of integers, calculate:
• The sum of all odd numbers
• The sum of all even numbers
Print both sums in a single line: odd sum followed by even sum

Input Format:
• First line: Integer N, number of elements
• Second line: N space-separated integers

Output Format:
• Two integers: sum of odd numbers and sum of even numbers

Constraints:
• 1 ≤ N ≤ 10³
• 1 ≤ arr[i] ≤ 10⁶

Sample Input:
5
46925
Sample Output:
14 12
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

34. Mean, Median, Mode

Problem Statement:
Given a sorted array of integers, compute the:
• Mean (average) — as a float rounded to 2 decimal places
• Median
• Mode (most frequent element — print the smallest one if multiple)

Input Format:
• First line: Integer N
• Second line: N sorted integers

Output Format:
• Three values on one line:
o Mean (rounded to 2 decimal places)
o Median (rounded to 2 decimal places if needed)
o Mode (as integer)

Constraints:
• 1 ≤ N ≤ 10⁴
• 0 ≤ A[i] ≤ 100

Sample Input:
8
12345566
Sample Output:
4.00 4.50 5

35. The Missing Number

Problem Statement:
You are given 99 unique integers from 1 to 100. Exactly one number is missing. Your task is to find the
missing number.

Input Format:
• One line: 99 space-separated integers

Output Format:
• Print the missing number

Constraints:
• Each number is between 1 and 100 (inclusive)
• No duplicates
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Sample Input (excerpt):

1 2 3 4 5 6 7 8 9 10 ... (skipping 92) ... 100
Sample Output:
92

36. Find Duplicate Number in Array

Problem Statement:
You are given an array of N integers where exactly one number appears twice and all others are unique. Find
and print that duplicate number.
You must not use inbuilt functions like [Link], set, or [Link]().

Input Format:
• First line: Integer N
• Second line: N space-separated integers

Output Format:
• One integer: the duplicate number

Constraints:
• 2 ≤ N ≤ 100
• 0 ≤ arr[i] ≤ 10⁹
• Only one duplicate exists

Sample Input:
6
5 4 10 9 21 10
Sample Output:
10

37. First and Last Occurrence

Problem Statement:
Given an array of integers and a value X, find the first and last index of X in the array. The array may contain
multiple occurrences of X.

Input Format:
• First line: Integer N
• Second line: N space-separated integers
• Third line: Integer X

Output Format:
• Two integers: first and last index of X (0-based)
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Constraints:
• 1 ≤ N ≤ 10³
• 1 ≤ A[i] ≤ 10⁵
• X ∈ A (X is guaranteed to be present at least once)

Sample Input:
10
1 3 5 7 9 11 3 13 15 3
3
Sample Output:
19

38. Unique Elements

Problem Statement:
Print all elements of the array that occur only once, in the order of their first appearance.
Do not use any inbuilt functions such as count, set, or collections.

Input Format:
• First line: Integer N
• Second line: N space-separated integers

Output Format:
• Space-separated unique elements in the order they appear

Constraints:
• 1 ≤ N ≤ 100
• 0 ≤ arr[i] ≤ 10⁹

Sample Input:
7
5 4 10 9 21 4 10
Sample Output:
5 9 21

39. Merge Two Sorted Arrays

Problem Statement:
You are given two sorted arrays A and B. Merge them into a single sorted array and print the result.
You may assume both arrays are sorted in non-decreasing order.

Input Format:
• First line: Integer n (size of array A)
• Second line: n integers
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

• Third line: Integer m (size of array B)

• Fourth line: m integers

Output Format:
• A single sorted array (space-separated)

Constraints:
• 1 ≤ n, m ≤ 10⁴
• -10⁹ ≤ A[i], B[i] ≤ 10⁹

Sample Input:
5
13579
4
2468
Sample Output:
123456789

40. Print Array A Using B

Problem Statement:
You are given two arrays:
• Array A of size n
• Array B of size m
For each index i in array B, check if B[i] is a valid index in array A (0 ≤ B[i] < n).
• If yes, print the element at that index in A.
• If no, print -1.

Input Format:
• First line: Integer n (size of A)
• Second line: n space-separated integers (A)
• Third line: Integer m (size of B)
• Fourth line: m space-separated integers (B)

Output Format:
• m space-separated integers as described above

Constraints:
• 1 ≤ n, m ≤ 100
• 0 ≤ A[i], B[i] ≤ 1000

Sample Input:
5
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

100 200 400 800 1000

6
4 2 0 6 10 0
Sample Output:
1000 400 100 -1 -1 100

41. Max Altitude

Problem Statement:
You are given an array of integers that represent the net gain or loss in altitude at each point of a journey.
Starting at altitude 0, your task is to find the highest altitude reached during the journey.

Input Format:
• First line: Integer n, the number of altitude changes
• Second line: n space-separated integers representing the changes

Output Format:
• Single integer: the maximum altitude reached

Constraints:
• 1 ≤ n ≤ 1000
• −10⁴ ≤ change[i] ≤ 10⁴

Sample Input:
5
-5 1 5 0 -7
Sample Output:
1

42. Longest Contiguous 1's

Problem Statement:
You are given a binary array (only 0s and 1s). Your task is to find the length of the longest contiguous
sequence of 1’s in the array.

Input Format:
• First line: Integer n
• Second line: n space-separated binary integers (0 or 1)

Output Format:
• Single integer: the maximum length of contiguous 1's

Constraints:
• 1 ≤ n ≤ 10⁵
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Sample Input:
10
1001011110
Sample Output:
4

43. Is Bitonic Sequence

Problem Statement:
Check whether the given array is a bitonic sequence.
An array is bitonic if:
• There exists an index i such that:
o All elements before index i are strictly increasing
o All elements after index i are strictly decreasing

Input Format:
• First line: Integer n
• Second line: n space-separated integers

Output Format:
• Print true if the array is bitonic, otherwise print false

Constraints:
• 3 ≤ n ≤ 10⁵

Sample Input:
4
0321
Sample Output:
true

44. MaxMin Partition

Problem Statement:
You are given an array D of integers.
Split the array into two non-empty parts E and F such that:
• E = D[0..i], F = D[i+1..n-1] for some valid i
• Your task is to minimize the absolute difference between max(E) and min(F).
Return the minimum absolute difference.

Input Format:
• First line: Integer n
• Second line: n space-separated integers
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Output Format:
• Single integer: the minimum absolute difference abs(max(E) - min(F))

Constraints:
• 2 ≤ n ≤ 10⁵
• −10⁶ ≤ D[i] ≤ 10⁶

Sample Input:
6
7 1 14 16 30 4
Sample Output:
2

45. Count the Valid Triplets

Problem Statement:
Given an array of integers, count the number of triplets (i, j, k) such that:
• i<j<k
• arr[i] + arr[j] + arr[k] == target

Input Format:
• First line: Integer N
• Second line: N space-separated integers
• Third line: Integer target

Output Format:
• One integer: the number of valid triplets

Constraints:
• 3 ≤ N ≤ 1000
• −10⁵ ≤ arr[i], target ≤ 10⁵

Sample Input:
6
123456
10
Sample Output:
3

46. Longest Subarray With Absolute Diff ≤ Limit

Problem Statement:
Given an array of integers and an integer limit, find the length of the longest continuous subarray such that
the absolute difference between any two elements in the subarray is less than or equal to limit.
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Input Format:
• Line 1: Integer n — number of elements in the array
• Line 2: n space-separated integers representing the array
• Line 3: Integer limit

Output Format:
• Single integer: length of the longest valid subarray

Constraints:
• 1 ≤ n ≤ 10^5
• 1 ≤ arr[i], limit ≤ 10^9

Example:
Input:
6
824723
4
Output:
3
Explanation: The longest valid subarray is [2, 4, 7] or [4, 7, 2] with max-min ≤ 4.

47. Minimum Swaps to Sort

Problem Statement:
Given an array of distinct integers, find the minimum number of swaps required to sort the array in ascending
order.
Input Format:
• Line 1: Integer n — size of the array
• Line 2: n distinct integers

Output Format:
• Single integer: minimum number of swaps required to sort the array

Constraints:
• 1 ≤ n ≤ 10^5
• All elements are unique

Example:
Input:
4
4321
Output:
2
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

48. Maximum Sum Increasing Subsequence

Problem Statement:
Given an integer array, find the sum of the maximum sum increasing subsequence in the array.

Input Format:
• Line 1: Integer n — size of the array
• Line 2: n space-separated integers

Output Format:
• Single integer: the maximum sum of an increasing subsequence

Constraints:
• 1 ≤ n ≤ 10^3
• 1 ≤ arr[i] ≤ 10^4

Example:
Input:
5
1 101 2 3 100
Output:
106

49. Count Subarrays with Product Less Than K

Problem Statement:
Given an array of positive integers and a positive integer k, count the number of contiguous subarrays where
the product of all elements is less than k.

Input Format:
• Line 1: Integer n
• Line 2: n space-separated positive integers
• Line 3: Integer k

Output Format:
• Single integer: count of such subarrays

Constraints:
• 1 ≤ n ≤ 10^5
• 1 ≤ arr[i] ≤ 1000
• 0 < k ≤ 10^6

Example:
Input:
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

4
10 5 2 6
100
Output:
8

50. Next Greater Element

Problem Statement:
For each element in the array, find the next greater element to its right. If no greater element exists, print -1.

Input Format:
• Line 1: Integer n
• Line 2: n space-separated integers

Output Format:
• A single line with n integers, where the ith integer is the next greater element of the ith element in the
array or -1 if none exists.

Constraints:
• 1 ≤ n ≤ 10^5
• −10^9 ≤ arr[i] ≤ 10^9

Sample Input:
4
4 5 2 10
Sample Output:
5 10 10 -1

51. Sort Array by Parity II

Problem Statement:
Given an array of integers arr of size n containing equal number of even and odd numbers, rearrange the
array so that elements at even indices are even, and elements at odd indices are odd.

Input Format:
• Line 1: Integer n (size of array)
• Line 2: n space-separated integers representing the array

Output Format:
• Print the rearranged array such that even indices contain even numbers and odd indices contain odd
numbers.

Constraints:
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

• 1 ≤ n ≤ 10^4
• The array contains equal number of even and odd numbers.

Sample Input:
4
4257
Sample Output:
4527

52. Number of Subarrays with Sum = K

Problem Statement:
Given an integer array, count the number of contiguous subarrays that sum up exactly to the integer k.

Input Format:
• Line 1: Integer n (size of array)
• Line 2: n space-separated integers
• Line 3: Integer k

Output Format:
• Single integer representing the count of contiguous subarrays summing to k.

Constraints:
• 1 ≤ n ≤ 10^5
• -10^4 ≤ arr[i] ≤ 10^4
• -10^9 ≤ k ≤ 10^9

Sample Input:
6
111211
3
Sample Output:
4

53. Count Occurrences of a Number in Sorted Array

Problem Statement:
Given a sorted array of integers and a target value, find how many times the target occurs in the array using
binary search (no linear search).

Input Format:
• Line 1: Integer n
• Line 2: n space-separated integers (sorted array)
• Line 3: Integer target
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Output Format:
• Single integer: count of target in the array.

Constraints:
• 1 ≤ n ≤ 10^5
• -10^9 ≤ arr[i], target ≤ 10^9

Sample Input:
7
1222345
2
Sample Output:
3

54. Find the Smallest Missing Positive Number

Problem Statement:
Given an unsorted array of integers, find the smallest positive integer that is missing from the array.

Input Format:
• Line 1: Integer n
• Line 2: n space-separated integers

Output Format:
• Single integer representing the smallest missing positive number.

Constraints:
• 1 ≤ n ≤ 10^5
• -10^5 ≤ arr[i] ≤ 10^5

Sample Input:
5
3 4 -1 1 2
Sample Output:
5

55. Rotate Array by K Positions

Problem Statement:
Given an array, rotate it to the right by k positions.

Input Format:
• Line 1: Two integers n and k
• Line 2: n space-separated integers
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Output Format:
• Single line of n space-separated integers representing the rotated array.

Constraints:
• 1 ≤ n ≤ 10^5
• 0 ≤ k ≤ 10^9
• -10^4 ≤ arr[i] ≤ 10^4

Sample Input:
52
12345
Sample Output:
45123

56. Find All Duplicates in an Array

Problem Statement:
Given an array of integers where each integer is between 1 and n (inclusive), and each integer appears once
or twice, return all elements that appear twice.

Input Format:
• Line 1: Integer n
• Line 2: n space-separated integers

Output Format:
• Single line with all duplicates (order does not matter), space-separated.

Constraints:
• 1 ≤ n ≤ 10^5
• 1 ≤ arr[i] ≤ n

Sample Input:
8
43278231
Sample Output:
23

57. Median of Sliding Window

Problem Statement:
Given an integer array and a sliding window size k, find the median of each sliding window as it moves from
left to right.

Input Format:
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

• Line 1: Two integers n and k

• Line 2: n space-separated integers

Output Format:
• A single line of n - k + 1 floats separated by space, each representing the median of the window. If
median is fractional, print decimal value.

Constraints:
• 1 ≤ k ≤ n ≤ 10^4
• -10^5 ≤ arr[i] ≤ 10^5

Sample Input:
53
1 3 -1 -3 5
Sample Output:
-1.0 -1.0 0.0

58. Longest Subarray of 1's After Deletion

Problem Statement:
Given a binary array, return the length of the longest subarray containing only 1's after deleting exactly one
element.

Input Format:
• Line 1: Integer n
• Line 2: n space-separated integers (each 0 or 1)

Output Format:
• Single integer: length of longest subarray of 1's after deleting one element.

Constraints:
• 1 ≤ n ≤ 10^5
• arr[i] ∈ {0,1}

Sample Input:
6
110111
Sample Output:
5

59. Count Good Pairs

Problem Statement:
Count the number of good pairs in an array. A pair (i, j) is good if i < j and nums[i] == nums[j].
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

Input Format:
• Line 1: Integer n
• Line 2: n space-separated integers

Output Format:
• Single integer: number of good pairs

Constraints:
• 1 ≤ n ≤ 100
• 1 ≤ nums[i] ≤ 100

Sample Input:
6
123113
Sample Output:
4

60. Search in Rotated Sorted Array

Problem Statement:
Given a rotated sorted array of unique integers and a target value, return the index of the target if found, else
return -1.

Input Format:
• Line 1: Integer n
• Line 2: n space-separated integers (rotated sorted array)
• Line 3: Integer target

Output Format:
• Single integer: index of target or -1 if not found.

Constraints:
• 1 ≤ n ≤ 10^4
• -10^4 ≤ nums[i], target ≤ 10^4

Sample Input:
7
4567012
0
Sample Output:
4
 Topic: 1. Arrays & Searching
Infosys HackWithInfy Preparatory Material
-- Compiled by Dr. K. V. Ramana

61. Maximum Average Subarray of Size K

Problem Statement:
Given an array of integers nums and an integer k, find the maximum average value of any contiguous
subarray of size k.

Input Format:
• Line 1: Two integers n and k
• Line 2: n space-separated integers

Output Format:
• A single float rounded to 5 decimal places — the maximum average of any subarray of size k.

Constraints:
• 1 ≤ n ≤ 10^5
• -10^4 ≤ nums[i] ≤ 10^4
• 1≤k≤n

Sample Input:
63
1 12 -5 -6 50 3
Sample Output:
15.66700