### Integer to Roman conversion - Leet Code Solution

Problem Statement Roman numerals are represented by seven different symbols: I…

October 01, 2020

Replace all spaces in a string with ‘%20’ (three characters). Do this in place and assume you have enough space in array

This is the simplest solution which many people might think.

- Iterate from left side (begining)
- After encountering a space, first shift entire array by 2 places.
- Put
`%20`

at consecutive location - Repeat this process

Obviously, if you see you need to shift the remaining array as many times as number of spaces. And, is not an efficient algorithm.

I will not put this silly code.

The complexity would be close to `O(n^2)`

If you start from left side, you saw we need to shift the array. What if we start from the right side.

- First calculate number of spaces in array, this will help in calculating the resultant last index
- Start iterating from right most side.
- Maintain two index counters. One for original array characters, other for resultant index positions.
- Start copying character one by one.
- If found space, just copy consecutive
`%20`

At the end, you will achieve the purpose. Lets see the code

```
private static int countSpaces(char[] input) {
int c = 0;
for (int i=0; i<input.length; i++) {
if (input[i] == ' ') {
c ++;
}
}
return c;
}
public static int replace(char[] input, int len) {
int spaces = countSpaces(input);
if (spaces == 0) return len;
int lastIndex = (len-1) + (2 * spaces);
int resultIndex = lastIndex;
for (int i=len-1; i>=0; i--) {
if (input[i] == ' ') {
//copy %20
input[lastIndex] = '0';
input[lastIndex-1] = '2';
input[lastIndex-2] = '%';
lastIndex -= 3;
}
else {
//copy actual characters
input[lastIndex] = input[i];
lastIndex --;
}
}
return resultIndex;
}
```

The complexity is `O(n)`

Problem Statement Roman numerals are represented by seven different symbols: I…

Problem Statement There are two sorted arrays nums1 and nums2 of size m and n…

This algorithm is very efficient one, and is classic example of Divide and…

Problem Statement Say you have an array prices for which the ith element is the…

This topic is one of the most common studied. When somebody started preparation…

Problem Statement Write a function that reverses a string. The input string is…

Introduction In this post we will see following: How to schedule a job on cron…

Introduction There are some cases, where I need another git repository while…

Introduction In this post, we will see how to fetch multiple credentials and…

Introduction I have an automation script, that I want to run on different…

Introduction I had to write a CICD system for one of our project. I had to…

Introduction Java log4j has many ways to initialize and append the desired…