DSA Problems with Solutions
Arrays(Linear & Binary Search):
1) Traversal in an array:
vector <int> a;
a = {2, 4, 5, 6, 7};
for (int i=0; i<a.size(); i++){
cout << a[i];
}
2) Sum of array:
vector <int> a;
a = {2, 4, 5, 6, 7};
int sum = 0;
for (int i=0; i<a.size(); i++){
sum += a[i];
}
cout << sum << endl;
3) Add elements in an array:
vector <int> a;
a = {2, 4, 5, 6, 7};
a.push_back(9);
for (int i=0; i<a.size(); i++){
cout << a[i];
}
4) Remove elements from array:
vector <int> a;
a = {2, 4, 5, 6, 7};
int elem_to_del = 6;
for (int i=0; i<a.size(); i++){
if (elem_to_del == a[i]){
a.erase(a.begin() + i);
}
}
for (int i=0; i<a.size(); i++){
cout << a[i];
1
}
5) Update elements of an array:
vector <int> a;
a = {2, 4, 5, 6, 7};
a[2] = 9;
for (int i=0; i<a.size(); i++){
cout << a[i];
}
6) Reverse an array:
vector <int> a;
a = {2, 4, 5, 6, 7};
vector<int> b(a.size());
for (int i=a.size(); i>0; i--){
b[i] = a[a.size() – 1 -i];
}
for (int i=0; i<b.size(); i++){
cout << b[i];
}
7) Swap alternates:
vector <int> a;
a = {2, 4, 5, 6, 7};
for (int i=0; i<a.size(); i+=2){
swap(a[i], a[i+1]);
}
for (int i=0; i<a.size(); i++){
cout << a[i] << endl;
}
8) Frequency of each element in an array:
vector <int> a;
a = {2, 4, 5, 6, 7};
map <int, int> mapp;
for (int i=0; i<a.size(); i++){
mapp[a[i]]++;
}
For (auto p : mapp){
cout << p.first << “ “ << p.second << endl;
2
}
9) Unique number of occurances:
vector <int> a;
a = {2, 4, 5, 6, 7};
map <int, int> mapp;
set <int> freqSet;
for (int i=0; i<a.size(); i++){
mapp[a[i]]++;
}
for (auto p : mapp){
if (frqSet.find(p.second) != freqSet.end()){
cout << “false”;
return 0;
}
freqSet.insert(p.second);
}
cout << “true”;
return 0;
10) Searching in an array:
vector <int> a;
a = {2, 4, 5, 6, 7};
int elem = 5;
for (int i=0; i<a.size(); i++){
if (a[i] == elem){
cout << I;
}
}
11) Find duplicates in an array:
vector <int> a;
a = {2, 3, 4, 3, 5, 6, 6, 5};
for (int i=0; i<a.size(); i++){
for (int j=i+1; j<a.size(); j++){
if (a[i] == a[j]){
cout << a[i] << " ";
}
}
}
3
12) Find unique element in an array:
vector <int> a;
a = {2, 3, 4, 3, 5, 6, 6, 5};
for (int i = 0; i < a.size(); i++) {
bool isUnique = true;
for (int j = 0; j < a.size(); j++) {
if (i != j && a[i] == a[j]) {
isUnique = false;
break;
}
}
if (isUnique) {
cout << a[i] << " ";
}
}
13) Find the sum of unique elements:
vector <int> a;
a = {2, 2, 3, 3, 4, 5, 6, 6, 7, 7};
int sum = 0;
for (int i = 0; i < a.size(); i++) {
bool isUnique = true;
for (int j = 0; j < a.size(); j++) {
if (i != j && a[i] == a[j]) {
isUnique = false;
break;
}
}
if (isUnique) {
sum += a[i];
}
}
cout << sum;
16) Find max/min in an array:
int maxVal = a[0];
for (int i=0; i<a.size(); i++){
if (a[i] > maxVal){
maxVal = a[i];
}
}
cout << maxVal;
4
int minVal = a[0];
for (int i=0; i<a.size(); i++){
if (a[i] < minVal){
minVal = a[i];
}
}
cout << minVal;
17) Remove duplicates from an array:
vector <int> a;
a = {2, 2, 3, 3, 4, 8, 5, 6, 6, 7, 7};
set<int> uniqueElem(a.begin(), a.end());
for (const int &elem : uniqueElem){
cout << elem << " ";
}
18) Move all zeroes to an end of array:
vector <int> a;
a = {2, 3, 0, 4, 0, 7, 0, 1};
for (int right=0; right<a.size(); right++){
if (a[right] != 0){
swap(a[right], a[left]);
left++;
}
}
for (int i=0; i<a.size(); i++){
cout << a[i];
}
19) Find 2nd largest element in an array:
int largest = INT_MIN;
int secondLargest = INT_MIN;
for (int i=0; i<a.size(); i++){
if (a[i] > largest){
secondLargest = largest;
largest = a[i];
}
else {
if (a[i] > secondLargest and a[i] < largest) {
secondLargest = a[i];
}
}
}
cout << secondLargest;
5
20) Best time to Buy and Sell Stock:
int mini = a[0];
int profit = 0;
for (int i=1; i<a.size(); i++){
int diff = a[i] - mini;
profit = max (profit, diff);
mini = min(mini, a[i]);
}
cout << profit;
24) Container With Most Water:
int left = 0;
int right = height.size() - 1;
int maxWater = 0;
while (left < right) {
int width = right - left;
int minHeight = min(height[left], height[right]);
int currWater = minHeight * width;
maxWater = max(maxWater, currWater);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
cout << maxWater;
22) Maximum subarray:
int sum = 0;
int maxi = nums[0];
for (int i=0; i<nums.size(); i++) {
sum = sum * nums[i];
maxi = max(maxi, sum);
if (sum < 0) {
sum = 0;
}
}
cout << maxi;
6
25) Find a missing number in an array:
vector<int> a;
a = {2, 3, 4, 5, 7, 8};
int n = a.size()
int totalSum = (n*(n+1))/2;
int arraySum = 0;
for (int i=0; i<n; i++) {
arraySum += a[i];
}
cout << totalSum – arraySum;
23) Maximum product subarray:
if (nums.empty()) return 0;
int maxProduct = nums[0];
int minProduct = nums[0];
int result = nums[0];
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] < 0) {
swap(maxProduct, minProduct);
}
maxProduct = max(nums[i], maxProduct * nums[i]);
minProduct = min(nums[i], minProduct * nums[i]);
result = max(result, maxProduct);
}
cout << result;
Binary Search:
2) Median of two arrays:
int m = nums1.size();
int n = nums2.size();
int* a = new int[m+n];
int i=0, j=0, k=0;
while (i<m && j<n) {
if (nums1[i] < nums2[j]){
a[k] = nums1[i];
i++;
}
else {
7
a[k] = nums2[j];
j++;
}
k++;
}
while (i<m) {
a[k] = nums1[i];
i++;
k++;
}
while (j<n) {
a[k] = nums2[j];
j++;
k++;
}
if ((m+n)%2 != 0) {
return a[(m+n)/2];
}
else {
int x = (m+n)/2;
double p = a[x];
double q = a[x-1];
return (p+q)/2;
}
