Solve Array related Data Structure problems in Salesforce Apex part 1. Learn collections and their usage.
Welcome to my article on apex . In this article we will try to solve the coding problems using apex and it's collections. We will solve some interesting problems step by step. We will learn problem solving and also efficient usage of collections.
What are we going to learn:
- How to approach a problem.
- How to pick the data structure.
- How to identify best collection to use.
- How to evaluate the running times.
If you want to learn collections first then you can refer to my previous blog on collections.
1.How do you find the missing numbers in a given integer array of 1 to 100?
//creating input data.
List<Integer> inputArray = new List<Integer>{1,2,3,49,67,0......100}
Solution 1: Using collection such as set :
Set<Integer> intSet = new Set<Integer>();
for(intger i =1;i<=100;i++){
intSet.add(i);
}
for(integer ele : inputArray){
if(ele >0 && ele <=100 && !intSet.contains(ele)){
print('missing number:' + ele)
}
}
2. Solution using List. :
use a list or array of size 100. let's call it buffer.
Iterate on the inputArray and store 1 at the index equal to the
element's value. when the operation will complete simply check in your
bufffer list for which index the entry is null. They will be the missing
numbers.
Integer[] buffer = new Integer[101];// first index is 0.
//populate the buffer list.
for(Integer ele : inputArray){
if(ele >0 && ele <=100){
//use ele as index .
buffer[ele] = 1 // adds 1 at position ele.
}
}
//check for which index the values are null in list.
for (Integer i =1;i <=100;i++){
if(buffer[i]==null){
system.debug('Missing no is : '+ i);
}
}
2. How will you find the frequency(no of times it is repeated) of each duplicate number in the given list or array?
1.one of the possible solution can be:
Use a Map. 50% of this problem solved by just thinking of map.
Rest of 50 % depends on the how will you use this map.
* for each element in input list store the element and it's counter in map.
Then iterate on Map and if counter is greater then 1, then print the ele with
the counter.
e.g for list 1,2,2,2
1: <1,1> 2: <1,1><2,1> 2: <1,1><2,2> 2: <1,1><2,3>
//code.
//inputList:
List<Integer> inputArray = new List<Integer>{1,2,3,2,2,3,4,5,1}
Map<Integer,Integer> frequencyMap = new Map<Integer,Integer>();
for (Integer ele : inputArray){
// map contains the ele
if(frequencyMap.ContainsKey(ele) && frequencyMap.get(ele)!=null){
int counter = frequencyMap.get(ele);
counter = counter + 1;
frequencyMap.put(ele,counter);
}
else {
// doesn't contain the element.
// initialize couter with zero.
frequencyMap.put(ele,0);
}
}
//print the repeated values.
for(integer key : frequencyMap.keySet()){
int count = frequncyMap.get(key);
if(count!=null && count >=1){
system.debug('ele : ' + ele + ' => frequency : ' + count);
}
}
3. How do you find the largest and smallest number in an unsorted Array?
//creating input data.
List<Integer> inputArray = new List<Integer>{1,2,3,49,67,0......100}
Logic here is take two max and min variable and initialize it with 0.
Iterate over the inputArray and check if max is less than the ele then ele is the new max. same if min is > than the ele then the ele is the new min.
1. Without recusrion:
Integer max = 0;
Integer min =0;
for(Integer i : inputArray){
if(max < i){
max =i;
}
if(min > i){
min =i;
}
}
2. With Recursion.
public class MinMaxClass {
Integer min=0;
Integer max =0;
List<Integer> inputArray = new List<Integer>{1,2,3,49,67,0......100}
}
MinMaxClass minMax = new MinMax();
MinMaxClass result = getMinMAX(inputArray,minMax,0,inputArray.size());
system.debug('max : + result.max + ' ' + 'min : ' + result.min);
public MinMaxClass getMinMAX(inputArray , minMax, i , n ){
Integer temp = inputArray[i];
minMax.max = minMax.max < temp ? temp: minMax.max;
minMax.min = minMax.min > temp ? temp; minMax.min;
//base case
if(n == 1){
return minMax;
}
else { //not base case
return getMinMax(inputArray,minMax, i+1,n-1);
}
}
4.How to find pairs in an array whose sum is equal to some number let's say 9?
problem is let's say there is an array : [1,2,3,4,5,6] . and we want to find pairs whose some is 6 : {1,5} {2,4}
// Input:
List<Integer> inputArray = new List<Integer>{1,2,3,5,6,7,9,4,8}
A Simple solution: We can use hash table to solve this problem.
for each value in input , we will store the value in hashtable and then we will search if 9-value exist in hash table or not. if yes then we will take that pair.
e.g: {1,4,10}
hash table T: []
Iterate on the list:
1: check if 9-1 exist , no => t.add(1) =>[1]
4: check if 9-4 exist, no => t.add(4) =>[1,4]
10: check if 9-8 exist , yes => get the pair <1,8>
Solutions using collection.
In Apex Map and set uses concept of hash table. here we just need to store the value so we will use set.
1. Using set:
//create a set and initialize it with
set<Integer> intSet = new Set<Integer>();
for(Integer ele : inputArray){
Integer other = 9 - ele;
if(intSet.contains(other )){
system.debug('pair --> ' + '<' + ele + ',' + other + '>');
}
intSet.add(ele);
}
!Important: Now a Question arises why we have used a hash table(set) , can't i use List? Yes: we can always use list. But then for each element in the input we will have to check whether the 9- ele exists in the list or not. this would take o(n) time for n elements so it will take n*o(n) = o(n*n). And set.contains(ele) takes only o(1) time so total time in case of set will be n*o(1) = o(n). So if we use set were are getting a lower running time.
But there is still an issue : Using set or list take O(n) space time. In simpler terms we need to use an extra table(set or list) to solve this. So it will work good for the finite sequences but for very large input we will have to maintain a larger table(set or list). Let's go for another solution which will not use any extra table.
2nd Solution :
Input T: [1,2,3,5,6,7,9,4,8]
Sort T : [1,2,3,4,5,6,7,8,9].
prob : find the pair of numbers whose sum is 9.
From the input T take one largest element and take one smallest element.
While ( smallest < largest ):
1. if the largest + smallest == 9 then print the pair and then take the second
largest as the largest and second smallest as the smallest.
2. if the larget + smallest > 9 then take the second largest as the largest
and repeat the process.
3. if the largest + smallest < 9 then take the second smallest as smallest and
repeat the process.
e.g sorted t: [1,2,3,4,5,6,7,8,9]
Take: smallest = 1 , largest = 9
check: 1+9 > 9 so : smallest = 1 , largest = 8
check : 1+8 =9 => print(<1,8>) => smallest = 2, largest = 7
check : 2+7 = 9 => print(<1,7>) => smallest = 3, largest =6
check : 3 + 6 = 9 => print(<3,6>) => smallest = 4, larset = 5
check : 4+5 = 9= > print(<4,5>) => smallest = 5, largest = 4. //stop here.
Apex code:
List<Integer> inputArray = new List<Integer>{1,2,3,4,5,6,7,8,9};
inputArray.sort();
Integer j = inputArray.size() - 1; // to hold the largest.
// i will hold the smallest.
Integer i = 0
while(i < j ){
Integer largest = inputArray[j];
Integer smallest = inputArray[i];
Integer sum = largest + smallest;
if(sum == 9){
print('the pair : ( '+ smallest + ',' + largest + ' )' );
//incremnt i , decrement j
i = i + 1;
j = j-1;
}
else if(sum > 9) {
j = j-1;
}
else if(sum < 9){
i = i-1;
}
}
Time: O(nlog(n)) for sorting . O(n) for Iterating. Total: O(n) + O(nlog(n)) = O(nlog(n)).
5. How do you reverse an array?
Input T: [1,2,3,5,6,7,9,4,8]
Solution using another array or List:
List<Integer> inputArray = new List<Integer>{1,2,3,5,6,7,9,4,8};
1 . Solution : inputArray.reverse(); // so easy.
2. Solution: Not using any list method.
List<Integer> reverseArray = new List<Integer>();
Integer size = inputArray.size();
for(Integer i = size -1 ; i>=0 ; i--){
reverseArray[size-i-1] = inputArray[i];
}
system.debug(reverseArray);
Time: O(n) for loop and O(1) for each assignment to the reverseArray.
Total : O(1)*O(n) = O(n) . Linear time.
3.Solution : Using list as stack.
stack is lifo . last in first out.
Integer size = inputArray.size() -1;
List<Integer> reverseArray = new List<Integer>();
while(size>=0) {
Integer ele = reverseArray.remove(size);
reverseArray.add(ele);
}
System.debug(reverseArray);
This code is same as the code 2. And it's look fancy then the other two but we
need to check if it is better than those other two in terms of time.
O(n) : for loop.
O(n) : avg for each iteration. (think about it. I wil explain it in the next
part of this series.)
Total time: O(n) * O(n) = O(n*n) . no linear. So it is not better then the code
snippet 2.
We have seen 5 problems related to array and we have tried to solve that with or without the collection methods. We have seen code efficiency in terms of time complexity also. In the next blog we will discuss some more problems. Thanks for reading this. Till Then Happy Salesforce and Happy coding.
#Salesforce #Salesforce_Apex #Data_Structure.
Really good.Looking for part 2 .Have u posted?
Very insightful post! Thanks a lot for covering this unique post. There're few logic above which might need some updates e.g. for large data sets, as far as I know O(n) is better than O(nlogn). Anyways, I hoped Salesforce Data Structure would be as vast as Java, else customization is definitely risky here based on Space/Time Complexity.
Really nice explanation KUMAR RAHUL . Appreciate that you try to cover these topics, otherwise most of us has the tendency to skip these core problem solving concepts in programming..👌👍
Nice Rahul! Keep it up😊👍